       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?
> 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:= Timing[p9a = permanent[mat];]

Out= {22.7825, Null}

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

Out= {0.240964, Null}

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

Out= 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