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
- speed of multiplying polynomials