Services & ResourcesWolfram ForumsMathGroup Archive

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

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[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.

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

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