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