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
- References:
- Permanent Computation Efficiency
- From: Sunt <sunting.05@gmail.com>
- Permanent Computation Efficiency