MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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