       Re: speed of multiplying polynomials

• To: mathgroup at smc.vnet.net
• Subject: [mg72716] Re: speed of multiplying polynomials
• From: Paul Abbott <paul at physics.uwa.edu.au>
• Date: Tue, 16 Jan 2007 03:19:38 -0500 (EST)
• Organization: The University of Western Australia
• References: <200701070439.XAA14676@smc.vnet.net> <eoa6fh\$mfs\$1@smc.vnet.net>

```In article <eoa6fh\$mfs\$1 at smc.vnet.net>, mcmcclure at unca.edu wrote:

> On Jan 12, 5:16 am, Paul Abbott <p... at physics.uwa.edu.au> wrote:
>
> > ... why does Mathematica not do this
> > automatically? For example, multiplication of large integers and
> > high-precision approximate numbers is done using interleaved schoolbook,
> > Karatsuba, three-way Toom-Cook and number-theoretic transform algorithms.
>
> I'm not sure that your comparison to integer multiplication
> (perhaps as fundamental an operation on as fundamental a
> data type as one can imagine) is a fair one. Your code
> suggests that we simply test if the input expressions are
> polynomials in a variable x; this is already far more
> complicated than checking for an integer.  Furthermore, we
> really need to know if the expression is a polynomial in
> *some* variable.  This seems quite a bit harder,
> particularly if the expression does not look like
> a polynomial.

I went on to write that:

> The total time of these operations is still less than that of direct
> multiplication, but there are now significant time penalties -- which
> makes one wonder why there is not an explicit Polynomial type or
> representation involving the coefficients and variables (perhaps
> invoking other tools such as sparse and/or packed arrays, as required
> for sparse polynmomials) so that multiplication and other polynomial
> operations is as fast as possible automatically?

Here I was asking why there is not an explicit Polynomial datatype. If
there was such a type, then one could either enter expressions as
polynomials -- and gain speed for certain operations -- or convert to
this type if required.

> More fundamentally, Expand and Collect are primarily
> symbolic operations while ListConvolve is primarily a
> numerical operation; each command works broadly, but is
> strongest in its own domain.

In what sense is ListConvolve a numerical operation? Do you mean it is
optimised for numerical arguments? Actually, as your code below shows,
it works fine with symbolic coefficients.

> Here's an example to illustrate the time complexity in
> various situation.  First, define a PolynomialMultiply
> function based on ListConvolve:
>
> PolynomialMultiply[Times[p1_, p2_], x_] := Module[
>     {c1, c2, c},
>     c1 = CoefficientList[p1, x];
>     c2 = CoefficientList[p2, x];
>     c = ListConvolve[c1, c2, {1, -1}, 0];
>     x^Range[0, Length[c] - 1].c] /;
>   PolynomialQ[p1, x] && PolynomialQ[p2, x];
>
> It is indeed quite fast when multiplying pre-expanded
> polynomials with integer coefficients.
>
> poly := Sum[Random[Integer, {1, 1000}]*x^i, {i, 0, 1000}];
> SeedRandom;
> PolynomialMultiply[poly*poly]; // Timing
> {0.009521 Second, Null}
>
> vs. Expand
>
> SeedRandom;
> Expand[poly*poly];//Timing
> {1.21226 Second,Null}
>
> But the Expand version works much faster with symbolic
> coefficients - even very simple ones
>
> p1 = Sum[a[n]x^n,{n,0,1000}];
> p2 = Sum[b[n]x^n,{n,0,1000}];
> PolynomialMultiply[p1*p2,x];//Timing
> {45.9369 Second,Null}
>
> Expand[p1*p2];//Timing
> {1.68533 Second,Null}

The majority of the time is taken testing whether p1 and p2 are
polynomials in x. Try

Timing[PolynomialQ[p1, x] && PolynomialQ[p2, x]]

to see this. If there was an explicit Polynomial datatype this test
would not be required, or at least would be _much_ faster. Indeed,
without this test, for the examples that I've tried, PolynomialMultiply
_beats_ Expand even for symbolic coefficients!

> Another observation: the different commands may return
> answers in different forms.  For example:
>
> p1 = (a+b)x+c;
> p2 = d*x+(e+f);
>
> Expand[p1*p2] //InputForm
> c*e + c*f + c*d*x + a*e*x + b*e*x + a*f*x + b*f*x + a*d*x^2 + b*d*x^2
>
> Expand[p1*p2,x] //InputForm
> c*e + c*f + c*d*x + (a + b)*e*x + (a + b)*f*x + (a + b)*d*x^2
>
> Collect[p1*p2,x] //InputForm
> c*e + c*f + (c*d + (a + b)*e + (a + b)*f)*x + (a + b)*d*x^2
>
> PolynomialMultiply[p1*p2,x] //InputForm
> c*(e + f) + (c*d + (a + b)*(e + f))*x + (a + b)*d*x^2
>
> Which is the correct answer?

Perhaps the best answer is the list of coefficients?

CoefficientList[p1 p2, x] // Expand
{c*e + c*f, c*d + a*e + b*e + a*f + b*f, a*d + b*d}

Cheers,
Paul

_______________________________________________________________________
Paul Abbott                                      Phone:  61 8 6488 2734
School of Physics, M013                            Fax: +61 8 6488 1014
The University of Western Australia         (CRICOS Provider No 00126G)
AUSTRALIA                               http://physics.uwa.edu.au/~paul

```

• Prev by Date: Re: simple modification of Solve
• Next by Date: Re: Difficulties with Complex-Modulus Series
• Previous by thread: Re: speed of multiplying polynomials
• Next by thread: Re: speed of multiplying polynomials