Re: Extracting polynomial coefficient?
- To: mathgroup@smc.vnet.net
- Subject: [mg11761] Re: Extracting polynomial coefficient?
- From: Allan Hayes <hay@haystack.demon.co.uk>
- Date: Thu, 26 Mar 1998 03:09:31 -0500
- References: <6emdjm$nno@smc.vnet.net> <6esone$68d@smc.vnet.net>
A way that seems to work well for sparse and for dense polynomials
solution3[expr_, vars_]:=
Module[{h},
Replace[Expand[Collect[expr, vars, h]],
{e_Plus:>List@@e, e_:>{e}}]/.
{u_.h[y_] -> {u,y}}]
My previous code (memory intensive; slow for sparse polynomials but
quick for dense ones)
solution1[ pol_, vars_] :=
Cases[
MapIndexed[ List, CoefficientList[pol, vars], {Length[vars]} ],
{c_?(#=!=0&), ind_} :> {Times @@ (vars^(ind-1)), c},
{Length[vars]}
]
Fred Simons' previous code ( quick for sparse polynomials but slow for
dense ones)
solution2[ pol_, vars_ ] := Module[ {ff},
ff /: ff[x_] ff[y_] := ff[x y];
ff /: ff[x_]^y_ := ff[x^y];
Cases[
Collect[ pp1=(pol /. (#->ff[#]&) /@ vars), ff[_] ],
x_. ff[y_] :> {y, x} ]
]
Comparison on sparse polynomials [100MHz PowerMac]
z := Random[Integer, {0, 10}]
pol =Sum[ (z+1) a^z b^z c^z d^z e^z , {100} ];
(sp1 =solution1[pol,{a,b,c,d,e}]);//Timing
{38.4167 Second,Null}
(sp2 =solution2[pol,{a,b,c,d,e}]);//Timing
{1.91667 Second,Null}
(sp3 =solution3[pol,{a,b,c,d,e}]);//Timing
{0.416667 Second,Null}
Sort[sp1]== Sort[sp2] == Sort[sp3]
True
Comparison on full polynomials
fullpoly[vars_,n_]:=
Plus@@Flatten[Outer[Times[Random[Integer,{1,(n+1)^(Length[vars])}],##]&,
Sequence@@(Evaluate[vars^#]&[Range[0,n]])
],Length[vars]-1]
fp= fullpoly[{a,b,c,d},4];
(fp1 =solution1[fp,{a,b,c,d,e}]);//Timing
{1.61667 Second,Null}
(fp2 =solution2[fp,{a,b,c,d,e}]);//Timing
{71.8 Second,Null}
(fp3 =solution3[fp,{a,b,c,d,e}]);//Timing
{2.03333 Second,Null}
Sort[fp1 ] == Sort[fp3]
True
But it turns out that solution2 misses constant terms
solution2[ 2 + 3 x,{x}]
{{x,3}}
But we do have
{Complement[fp3,fp2], Complement[fp2,fp3]}
{{{1,610}},{}}
--
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