Re: speed of multiplying polynomials

*To*: mathgroup at smc.vnet.net*Subject*: [mg72635] Re: speed of multiplying polynomials*From*: mcmcclure at unca.edu*Date*: Sat, 13 Jan 2007 04:09:53 -0500 (EST)*References*: <200701070439.XAA14676@smc.vnet.net><ent4s4$etq$1@smc.vnet.net>

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. What if the polynomial is not pre-expanded? For example: CoefficientList[(x+a)(x-b),x] {-a b,a-b,1} This has serious consequences for the time complexity of of an algorithm using List Convolve, even if a and b are integers. 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. I think it is reasonable, even necessary, to expect users to understand this - in much the same way that users need to understand when to use Solve vs NSolve. Although, this is an admittedly subtle situation. 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} 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? MM

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