Re: Extracting polynomial coefficients?
- To: mathgroup@smc.vnet.net
- Subject: [mg11751] Re: Extracting polynomial coefficients?
- From: Allan Hayes <hay@haystack.demon.co.uk>
- Date: Thu, 26 Mar 1998 03:09:19 -0500
Fred Simons notes that in his original posting Thomas Bell Thomas wrote
that he had a "very long" polynomial and give new solution (solution2
below) that is much quicker my earlier solutions (solution1 below) on
the examples tested. However it seems that solution2 is faster for
sparse polynomials (where many coefficients are zero) and solution1 is
faster for full polynomials (where many coefficients are non-zero). So
it all depends on what "very long" means.
The solution
solution1[ pol_, vars_] := Cases[
MapIndexed[ List, CoefficientList[pol, vars], {Length[vars]} ],
{c_?(#=!=0&), ind_} :> {Times @@ (vars^(ind-1)), c},
{Length[vars]}
]
can be very wasteful in that it finds all coefficients when only a few
may be non zero, and then has to get rid of the unwanted ones. Not only
does this slow it down, it also uses a lot of menory.
Because of this
solution2[ pol_, vars_ ] := Module[ {ff},
ff /: ff[x_] ff[y_] := ff[x y];
ff /: ff[x_]^y_ := ff[x^y];
Cases[
Collect[ pol /. (#->ff[#]&) /@ vars, ff[_] ],
x_. ff[y_] :> {y, x} ]
]
is considerably faster when many of the coefficients are zero.
With
z := Random[Integer, {0, 10}]
pol =Sum[ (z+1) a^z b^z c^z d^z e^z , {100} ];
we get
solution1[pol,{a,b,c,d,e}];//Timing
{32.7333 Second, Null}
solution2[pol,{a,b,c,d,e}];//Timing
{2.33333 Second, Null}
However pol has at most 100 non-zero coefficients non-zero out of maybe
11^5. When most coefficients are non-zero then solution1 (which makes
more use of internal algorithms) turns out to be much faster.
For example:
Using the following to genererate polynomials with all coefficients non
zero
poly[vars_,n_]:=
Plus@@Flatten[Outer[Times[Random[Integer,{1,(n+1)^(Length[vars])}],##]&,
Sequence@@(Evaluate[vars^#]&[Range[0,n]])
],Length[vars]-1]
(
poly[{a,b},2]
2 2 2 2 2 2 7 + 9 a + 2
a + 9 b + 7 a b + a b + b + 3 a b + 8 a b )
With
fp = poly[{a,b,c,d},4];
we get
solution2[fp,{a,b,c,d}];//Timing
{61.5667 Second, Null}
solution1[fp,{a,b,c,d}];//Timing
{1.5 Second, Null}
So we have the usual dilemma of sparse structures and full ones
requiring different approaches - perhaps a combination of the two codes
might automatically scan what it has been given before choosing which
code to use.
The following is a slightly faster than solution1
solution1a [pol_, vars_] :=
DeleteCases[
Flatten[
MapIndexed[ {Times@@(vars^(#2-1)),#}&,
CoefficientList[pol, vars], {Length[vars]}
],
Length[vars]-1
],
{_,0}
]
solution1a[fp,{a,b,c,d}];//Timing
{1.43333 Second, Null}
--
Allan Hayes
Training and Consulting
Leicester, UK
hay@haystack.demon.co.uk
http://www.haystack.demon.co.uk
voice: +44 (0)116 271 4198
fax: +44 (0)116 271 8642