       Re: speed of multiplying polynomials

• To: mathgroup at smc.vnet.net
• Subject: [mg72619] Re: speed of multiplying polynomials
• From: Paul Abbott <paul at physics.uwa.edu.au>
• Date: Fri, 12 Jan 2007 06:01:48 -0500 (EST)
• Organization: The University of Western Australia
• References: <200701070439.XAA14676@smc.vnet.net> <ent4s4\$etq\$1@smc.vnet.net>

```In article <ent4s4\$etq\$1 at smc.vnet.net>, Carl Woll <carlw at wolfram.com>
wrote:

> dmharvey at math.harvard.edu wrote:
>
> >Hi,
> >
> >I'm trying to figure out how fast mathematica can multiply polynomials
> >with integer coefficients. I don't know mathematica well at all, but I
> >had a friend write me a mathematica program to test this. It look like
> >on a regular desktop machine it can multiply e.g. degree 1000
> >polynomials with coefficients in the range 0 <= x <= 1000 in about 1.3
> >seconds.
> >
> >This is ludicrously slow compared to some other computer algebra
> >systems, which can do this multiplication in about 0.0003
> >seconds. I can't believe mathematica is in the order of 10000 times
> >slower for this simple task. I think perhaps we are doing something
> >wrong. Can anyone suggest a way of coaxing mathematica into doing this
> >kind of arithmetic at a comparable pace?
> >
> >Many thanks
> >
> >David
> >
> >
> I think the problem is with the representation of a polynomial. Assuming
> we are dealing with univariate polynomials, we can represent the
> polynomial as a list of coefficients:
>
> c = {900, 801, etc}
>
> or as a polynomial with explicit multiplications and additions:
>
> p = 900 + 801*x + etc.
>
> If we work with lists, we can use ListConvolve to do the multiplication.
> If we work with polynomials, we will probably use Expand. Here is an
> example multiplying two polynomials in both ways. Here are the coefficients:
>
> In:=
> c1 = Table[Random[Integer, {0, 1000}], {1001}];
> c2 = Table[Random[Integer, {0, 1000}], {1001}];
>
> Here are the equivalent polynomials:
>
> In:=
> p1 = x^Range[0, 1000] . c1;
> p2 = x^Range[0, 1000] . c2;
>
> Here we time multiplication using ListConvolve:
>
> In:=
> c = ListConvolve[c1, c2, {1, -1}, 0]; // Timing
> Out=
> {0. Second, Null}
>
> Here we time multiplication using Expand:
>
> In:=
> p = Expand[p1 p2]; // Timing
> Out=
> {2.25 Second, Null}
>
> Finally, we check that the two approaches yield the same result:
>
> In:=
> c === CoefficientList[p, x]
> Out=
> True
>
> So, if one is interested in multiplying large, dense univariate
> polynomials in Mathematica, the fastest approach is to use ListConvolve.

All this is true but the essential question -- one that David Harvey
alluded to in his original post -- is 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.

In other words if a computation involves multiplying large, dense
univariate polynomials then _internally_ Mathematica should use
ListConvolve. Now, given two polynomials, it takes time to check that
each _is_ a polynomial,

PolynomialQ[p1, x]; // Timing
PolynomialQ[p2, x]; // Timing

time to extract the coefficients,

c1 = CoefficientList[p1, x]; // Timing
c2 = CoefficientList[p2, x]; // Timing

time to multiplication using ListConvolve:

c = ListConvolve[c1, c2, {1, -1}, 0]; // Timing

and time to reconstruct the resulting polynomial

p = x^Range[0, Length[c] - 1] . c; // Timing

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?

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: Limit and Root Objects
• Next by Date: Re: FullSimplify and HypergeometricPFQ
• Previous by thread: Re: speed of multiplying polynomials
• Next by thread: Re: speed of multiplying polynomials