MathGroup Archive 2007

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

Search the Archive

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


  • Prev by Date: Re: simple modification of Solve
  • Next by Date: Re: Difficulties with Complex-Modulus Series
  • Previous by thread: Re: speed of multiplying polynomials
  • Next by thread: Re: speed of multiplying polynomials