Re: Permanent Computation Efficiency
- To: mathgroup at smc.vnet.net
- Subject: [mg105049] Re: [mg105035] Permanent Computation Efficiency
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Thu, 19 Nov 2009 05:22:56 -0500 (EST)
- References: <200911181200.HAA04436@smc.vnet.net>
Hi,
The key observation (for me anyway) was that while Times
@@ (m.v) computes a symbolic product of Length[m] terms, each of which is a
sum of Length[m] terms, it does not expand this product. Were it expanded
(you may try wrapping Expand around Times @@ (m.v) , but beware of the huge
memory consumption that this will cause), it would have been a huge number
of terms, and your expectation would probably be confirmed (hard to predict
though since symbolic addition/multiplication doesn't really do much and
thus doesn't take much time, but OTOH it takes lots of memory to keep the
resulting expanded expression. Seems like this is still faster than your
second solution, but more memory - hungry). Now, it appears that Coefficient
is a pretty smart function which can deduce the coefficient of some power(s)
of the variable(s) without expanding the product, but rather probably using
some combinatorial arguments.
Regards,
Leonid
On Wed, Nov 18, 2009 at 4:00 AM, Sunt <sunting.05 at gmail.com> 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!
>
>
- References:
- Permanent Computation Efficiency
- From: Sunt <sunting.05@gmail.com>
- Permanent Computation Efficiency