Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Permanent Computation Efficiency

• To: mathgroup at smc.vnet.net
• Subject: [mg105103] Re: [mg105035] Permanent Computation Efficiency
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sat, 21 Nov 2009 03:33:01 -0500 (EST)
• References: <200911181200.HAA04436@smc.vnet.net> <4B0427ED.5080309@wolfram.com> <eafb5fea0911190206w3555b52i12aec24f66479d06@mail.gmail.com>

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
> [...]

I was confused for some time about the complexity of permanent2. In the 
numeric case it behaves like O(2^n), in the symbolic cases I tried it 
seemed to be O(n!). I now think I understand this.

It is easy to check that O(2^n) sub-permanents get created when one 
computes a permanent of an nxn from scratch (this means we erase all 
stored DownValues after finishing a computation and before starting the 
next one).

Here is a specific example. It shows the 2^n complexity, both in speed 
and memory usage. That latter is not hard to reason from basic 
principles, and indeed that also gives a measure of the expected 
performance. Or at least a lower bound, as we'll see momentarily.

mat[n_] := Array[m, {n,n}];

Table[
   Clear[permanent2];
   permanent2[m_] /; Length[m]==1 := m[[1,1]];
   permanent2[m_] := permanent2[m] = With[{mp=Drop[m,None,1]},
     Apply[Plus, Table[m[[j,1]]*permanent2[Drop[mp,{j}]],
       {j,Length[m]}]]];
   {First[Timing[permanent2[mat[j]/.m[ii_,jj_]:>ii+jj^2]]],
     Length[DownValues[permanent2]]},
   {j,8,18}]

Out[12]= {{0.007999, 249}, {0.017998, 504}, {0.035994, 1015},
    {0.077988, 2038}, {0.167975, 4085}, {0.370943, 8180},
    {0.797878, 16371}, 1.74074, 32754}, {3.70044, 65521},
    {7.8638, 131056}, {16.7045, 262127}}

Now we'll try the purely symbolic case (of necessity, using smaller 
dimensions).

Table[
   Clear[permanent2];
   permanent2[m_] /; Length[m]==1 := m[[1,1]];
   permanent2[m_] := permanent2[m] = With[{mp=Drop[m,None,1]},
     Apply[Plus, Table[m[[j,1]]*permanent2[Drop[mp,{j}]],
       {j,Length[m]}]]];
   {First[Timing[permanent2[mat[j]]]],
     Length[DownValues[permanent2]]},
   {j,7,11}]

Out[13]= {{0.009998, 122}, {0.037994, 249}, {0.249962, 504},
    {2.05569, 1015},  {21.8357, 2038}}

We are storing O(2^n) sub-permanents. But the timing is clearly O(n!). 
This seeming mystery is resolved by checking the sizes (measured by 
LeafCount) of the results. They are grwoing as N!, hence the time needed 
to produce them must be as bad. Here is the code, barely modified, that 
shows this.

Table[
   Clear[permanent2];
   permanent2[m_] /; Length[m]==1 := m[[1,1]];
   permanent2[m_] := permanent2[m] = With[{mp=Drop[m,None,1]},
     Apply[Plus, Table[m[[j,1]]*permanent2[Drop[mp,{j}]],
       {j,Length[m]}]]];
   {First[Timing[permanent2[mat[j]]]],
     LeafCount[permanent2[mat[j]]],
     Length[DownValues[permanent2]]},
   {j,7,11}]
 

Out[14]= {{0.011998, 53376, 122}, {0.037994, 427041, 249},
     {0.240964, 3843406, 504}, {2.08568, 38434101, 1015},
     {21.9807, 422775156, 2038}}

The upshot is that expression swell is making this purely symbolic case 
show the n! behavior. In contrast, the integer case when done with 
cached sub-permanents, is "merely" exponential in behavior.

Daniel Lichtblau
Wolfram Research

• References:
  • Permanent Computation Efficiency
    • From: Sunt <sunting.05@gmail.com>