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[1]; > PolynomialMultiply[poly*poly]; // Timing > {0.009521 Second, Null} > > vs. Expand > > SeedRandom[1]; > 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

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