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