|
[Date Index]
[Thread Index]
[Author Index]
Re: Re: Permanent Computation Efficiency
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
Prev by Date:
Re: Re: Undo in Mathematica
Next by Date:
More Efficient Method
Previous by thread:
Re: Permanent Computation Efficiency
Next by thread:
Re: Permanent Computation Efficiency
|
