Re: Permanent Computation Efficiency

*To*: mathgroup at smc.vnet.net*Subject*: [mg105067] Re: [mg105035] Permanent Computation Efficiency*From*: åæ <sunt05 at mails.tsinghua.edu.cn>*Date*: Thu, 19 Nov 2009 07:25:17 -0500 (EST)*References*: <200911181200.HAA04436@smc.vnet.net> <4B0427ED.5080309@wolfram.com>

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 On Thu, Nov 19, 2009 at 12:59 AM, Daniel Lichtblau <danl at wolfram.com> wrote: > 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 > > > > > >

**Follow-Ups**:**Re: Re: Permanent Computation Efficiency***From:*Daniel Lichtblau <danl@wolfram.com>

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