Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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?


  • Prev by Date: Re: I broke the sum into pieces
  • Next by Date: Re: Question about MeshFunctions (Plot function)
  • Previous by thread: Re: Re: Permanent Computation Efficiency
  • Next by thread: Re: Permanent Computation Efficiency