MathGroup Archive 2009

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

Search the Archive

Permanent Computation Efficiency

  • To: mathgroup at smc.vnet.net
  • Subject: [mg105035] Permanent Computation Efficiency
  • From: Sunt <sunting.05 at gmail.com>
  • Date: Wed, 18 Nov 2009 07:00:53 -0500 (EST)

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!


  • Prev by Date: subscripts in function definitions
  • Next by Date: Re: Sound Functions Crash Kernel
  • Previous by thread: Re: subscripts in function definitions
  • Next by thread: Re: Permanent Computation Efficiency