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!
- Follow-Ups:
- Re: Permanent Computation Efficiency
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Permanent Computation Efficiency
- From: Leonid Shifrin <lshifr@gmail.com>
- Re: Permanent Computation Efficiency