Services & ResourcesWolfram ForumsMathGroup Archive

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

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>