Re: Permanent Computation Efficiency

*To*: mathgroup at smc.vnet.net*Subject*: [mg105077] Re: Permanent Computation Efficiency*From*: Sunt <sunting.05 at gmail.com>*Date*: Fri, 20 Nov 2009 06:38:30 -0500 (EST)*References*: <200911181200.HAA04436@smc.vnet.net> <he372o$err$1@smc.vnet.net>

On Nov 19, 6:36 pm, Leonid Shifrin <lsh... at gmail.com> wrote: > 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... 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! Thank you! Could you please tell me what combinatorial knowledge is in need to understand the function Coefficient?

**References**:**Permanent Computation Efficiency***From:*Sunt <sunting.05@gmail.com>