MathGroup Archive 2009

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

Search the Archive

Re: Permanent Computation Efficiency

  • To: mathgroup at smc.vnet.net
  • Subject: [mg105063] Re: [mg105035] Permanent Computation Efficiency
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Thu, 19 Nov 2009 05:25:37 -0500 (EST)
  • References: <200911181200.HAA04436@smc.vnet.net>

Sunt wrote:
> Hi All,
> Recently I've been dealing with one problem of permanent computation
> and got puzzled about two algorithms on it.
> 
> I've find a defined function from Mathworld(http://
> mathworld.wolfram.com/Permanent.html) as bellow:
> Permanent[m_List] := With[{v = Array[x, Length[m]]}, Coefficient[Times
> @@ (m.v), Times @@ v]]
> Meanwhile, according to Laplace Expansion Theorem, we have another
> function for permanent computation(expanding a permanent by the first
> row):
> LPermanent[m_List?(Length[#] == 1 &)] := Flatten[m] // First;
> LPermanent[m_List] := Module[  {n = Length[m], v, mm},
>   v = m[[All, 1]];
>   mm = m[[All, 2 ;; -1]];
>   (v.Table[LPermanent[Delete[mm, i]], {i, n}])
>     ]
> 
> Comparison of the two functions is quite interesting but puzzling, the
> former is much better than the other.
> Running the two function with the same 10*10 matrix with Timing[]
> appended, the former finished in 0.s while the other a much slower
> 779.912s!
> However, according to the computation complexity analysis, the latter
> is expected as a better one.
> 
> Is there something I didn't understand about?
> Looking forward to your reply!
> Thanks a lot!

We had a similar discussion in house around ten years ago. (I found it 
in an old email box). First, your second approach will be slower unless 
you memo-ize intermediate results. Can be done as below.

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]}]]]

This of course means you run a risk of memory overflow if dimensions get 
too large. But if you do nothing to store intermediate results, this 
method is about as slow as possible.

I will also mention that the relative speeds will depend on the type of 
matrix in question, e.g. symbolic vs. numeric.

Here is a dense symbolic example, with all entries distinct and 
algebraically independent.

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

In[5]:= Timing[p9a = permanent[mat[9]];]

Out[5]= {22.7825, Null}

In[6]:= Timing[p9b = permanent2[mat[9]];]

Out[6]= {0.240964, Null}

In[10]:= Expand[p9a]===Expand[p9b]

Out[10]= True

Might get different results with numeric matrices. Or sparse matrices.

Daniel Lichtblau
Wolfram Research







  • Prev by Date: Re: Mathematica scoping / contexts / variable localization
  • Next by Date: Re: Mathematica scoping / contexts / variable localization
  • Previous by thread: Re: Permanent Computation Efficiency
  • Next by thread: Re: Permanent Computation Efficiency