Re: Re: Permanent Computation Efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg105072] Re: [mg105067] Re: [mg105035] Permanent Computation Efficiency
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Fri, 20 Nov 2009 06:37:30 -0500 (EST)
- References: <200911181200.HAA04436@smc.vnet.net> <4B0427ED.5080309@wolfram.com> <200911191225.HAA19355@smc.vnet.net>
Sunt wrote:
> Daniel, thank you for your suggestion!
>
> However, I still didn't quite know the mechanism of the function Coefficient[].
> And how to determine the computation complexities of the two permanent[]
> functions by big O notation?
> In my opinion, the complexity of permanent2[] is O(n!). Is it right?
>
> Thanks a lot!
>
> Sunt
Coefficient is taking derivatives, without expanding the expression. Not
sure what is the complexity of this approach. It cannot be better than
exponential, if i recall permanent complexity correctly. Probably
factorial in dimension of the matrix.
The complexity of permanent2[] seems to be O(n!) for basic symbolic
matrices of the sort I used. I base that on some simple timings using
mat[n_] := Array[m, {n,n}];
Timing[p9b = permanent2[mat[9]];]
Timing[p10b = permanent2[mat[10]];]
Timing[p11b = permanent2[mat[11]];]
Since the sub-permenents share sub-sub-computations, and memo-ization is
used, I'm not sure what is the complexity in general. When I use integer
entries, the methods behave as though they might be better than O(n!),
and indeed permanent2 seems to get five times slower for every jump of 2
in n. If this reflects the actual complexity, the improvement over n! is
due to substantial use of memory.
Daniel Lichtblau
Wolfram Research
- References:
- Permanent Computation Efficiency
- From: Sunt <sunting.05@gmail.com>
- Re: Permanent Computation Efficiency
- From: åæ <sunt05@mails.tsinghua.edu.cn>
- Permanent Computation Efficiency