Services & ResourcesWolfram ForumsMathGroup Archive

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

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