Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: speed of multiplying polynomials

• To: mathgroup at smc.vnet.net
• Subject: [mg72566] Re: [mg72554] speed of multiplying polynomials
• From: Carl Woll <carlw at wolfram.com>
• Date: Mon, 8 Jan 2007 05:32:57 -0500 (EST)
• References: <200701070439.XAA14676@smc.vnet.net>

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[1]:=
c1 = Table[Random[Integer, {0, 1000}], {1001}];
c2 = Table[Random[Integer, {0, 1000}], {1001}];

Here are the equivalent polynomials:

In[3]:=
p1 = x^Range[0, 1000] . c1;
p2 = x^Range[0, 1000] . c2;

Here we time multiplication using ListConvolve:

In[5]:=
c = ListConvolve[c1, c2, {1, -1}, 0]; // Timing
Out[5]=
{0. Second, Null}

Here we time multiplication using Expand:

In[6]:=
p = Expand[p1 p2]; // Timing
Out[6]=
{2.25 Second, Null}

Finally, we check that the two approaches yield the same result:

In[7]:=
c === CoefficientList[p, x]
Out[7]=
True

So, if one is interested in multiplying large, dense univariate 
polynomials in Mathematica, the fastest approach is to use ListConvolve.

Carl Woll
Wolfram Research

• References:
  • speed of multiplying polynomials
    • From: dmharvey@math.harvard.edu