RE: Extracting polynomial coef
- To: mathgroup@smc.vnet.net
- Subject: [mg11781] RE: [mg11744] Extracting polynomial coef
- From: Ersek_Ted%PAX1A@mr.nawcad.navy.mil
- Date: Sat, 28 Mar 1998 00:25:18 -0500
It seems like use of Coeficient[poly, pattn] will help a lot. Consider
the high order polynomial below.
In[1]:=
Clear[x,y,z];
poly=(x+2y-z)^500;
In[2]:=
Timing[Coefficient[poly, x^120*y^80*z^300]]
Out[2]=
{0.33 Second,
1006661767774354619621242915295837151924640944383364495757579942810390538544\
6761497343959275998230703510951162719835501677912005898799273321799393032263
96\
0370321102046617456644078007368907442050765790290809603381303273586688000}
Ted Ersek
----
|<<File Attachment: 00000000.TXT>>
|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
|