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>
- Permanent Computation Efficiency