Re: Re: Extracting polynomial coefficients?
- To: mathgroup@smc.vnet.net
- Subject: [mg11744] Re: [mg11602] Re: Extracting polynomial coefficients?
- From: "Fred Simons" <wsgbfs@win.tue.nl>
- Date: Thu, 26 Mar 1998 03:09:11 -0500
The problem raised by Thomas Bell (how to find which combinations of the
variables are in a very long polynomial and to find the corresponding
coefficients) has some interesting features.
Allan Hayes published a very ingenious and elegant solution (as usual)
making use of CoefficientList and MapIndexed. It is based on the idea
that the coefficient of a^i b^j c^k d^m can be found in the
coefficientlist at position {i+1, j+1, k+1, m+1}, so we find all terms
of the polynomial by selecting the coefficients unequal to zero from
the coefficientlist; the corresponding exponents of the variables are
found from the position of the selected coefficient. Here is his
implementation:
solution1[ pol_, vars_] := Cases[
MapIndexed[ List, CoefficientList[pol, vars], {Length[vars]} ],
{c_?(#=!=0&), ind_} :> {Times @@ (vars^(ind-1)), c},
{Length[vars]}
]
In his origial posting, Thomas wrote that he had a very long polynomial.
That suggests that using the function CoefficientList would result in
huge structures, so I was looking for a construction that does not make
use of CoefficientList.
To explain the idea, let us assume that the variables are a, b, c and d.
We 'mark' these variables by replacing them with ff[a], ff[b], ff[c]
and ff[d]. Now we take care that in each term of the polynomial the
factors ff automatically combine to one factor ff by defining
ff /: ff[x_] ff[y_] := ff[x y]
ff /: ff[x_]^y_ := ff[x^y]
The result is that each term c a^i b^j c^k d^m of the polynomial has
been replaced with c ff[a^i b^j c^k d^m]. Collecting ff[_] combines
corresponding terms and now it is straightforward to find the
combinations of a, b, c and d that occur in the polynomial and the
corresponding coefficient. Here is the implementation:
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} ]
]
Let us have a look at the performance of these solutions by applying
them to a long polynomial. With the following commands we construct a
polynomial consisting of 100 terms of degree at most 10 in each of the
seven variables.
z := Random[Integer, {0, 10}]
pol =Sum[ (z+1) a^z b^z c^z d^z e^z f^z g^z, {100} ];
Taking vars={a}, both solutions are fast, Allan Hayes' solution being
about twice as fast as mine. With vars={a,b,c,d}, solution1 needs 0.72
seconds and solution2 0.49 seconds. With vars={a,b,c,d,e} we find 23.73
seconds for solution1 and 0.61 seconds for solution2. With 6 variables,
solution1 is hardly usefull (580.07 seconds) and solution2 takes 2.2
seconds.
A similar behaviour is obtained when we increase the degree of the
terms. When we reconstruct the polynomial pol with z := Random[Integer,
{50, 60}], for one and two variables both solutions take less than a
second, solution1 being faster than solution2. With 3 variables,
solution1 took 8.73 seconds and solution2 0.55 seconds. With
vars={a,b,c,d} I had to interrupt the computation with solution1, and
solution2 needed only 0.6 second.
Fred Simons
Eindhoven University of Technology