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