[Date Index]
[Thread Index]
[Author Index]
Re: speed of multiplying polynomials
*To*: mathgroup at smc.vnet.net
*Subject*: [mg72619] Re: speed of multiplying polynomials
*From*: Paul Abbott <paul at physics.uwa.edu.au>
*Date*: Fri, 12 Jan 2007 06:01:48 -0500 (EST)
*Organization*: The University of Western Australia
*References*: <200701070439.XAA14676@smc.vnet.net> <ent4s4$etq$1@smc.vnet.net>
In article <ent4s4$etq$1 at smc.vnet.net>, Carl Woll <carlw at wolfram.com>
wrote:
> dmharvey at math.harvard.edu wrote:
>
> >Hi,
> >
> >I'm trying to figure out how fast mathematica can multiply polynomials
> >with integer coefficients. I don't know mathematica well at all, but I
> >had a friend write me a mathematica program to test this. It look like
> >on a regular desktop machine it can multiply e.g. degree 1000
> >polynomials with coefficients in the range 0 <= x <= 1000 in about 1.3
> >seconds.
> >
> >This is ludicrously slow compared to some other computer algebra
> >systems, which can do this multiplication in about 0.0003
> >seconds. I can't believe mathematica is in the order of 10000 times
> >slower for this simple task. I think perhaps we are doing something
> >wrong. Can anyone suggest a way of coaxing mathematica into doing this
> >kind of arithmetic at a comparable pace?
> >
> >Many thanks
> >
> >David
> >
> >
> I think the problem is with the representation of a polynomial. Assuming
> we are dealing with univariate polynomials, we can represent the
> polynomial as a list of coefficients:
>
> c = {900, 801, etc}
>
> or as a polynomial with explicit multiplications and additions:
>
> p = 900 + 801*x + etc.
>
> If we work with lists, we can use ListConvolve to do the multiplication.
> If we work with polynomials, we will probably use Expand. Here is an
> example multiplying two polynomials in both ways. Here are the coefficients:
>
> In[1]:=
> c1 = Table[Random[Integer, {0, 1000}], {1001}];
> c2 = Table[Random[Integer, {0, 1000}], {1001}];
>
> Here are the equivalent polynomials:
>
> In[3]:=
> p1 = x^Range[0, 1000] . c1;
> p2 = x^Range[0, 1000] . c2;
>
> Here we time multiplication using ListConvolve:
>
> In[5]:=
> c = ListConvolve[c1, c2, {1, -1}, 0]; // Timing
> Out[5]=
> {0. Second, Null}
>
> Here we time multiplication using Expand:
>
> In[6]:=
> p = Expand[p1 p2]; // Timing
> Out[6]=
> {2.25 Second, Null}
>
> Finally, we check that the two approaches yield the same result:
>
> In[7]:=
> c === CoefficientList[p, x]
> Out[7]=
> True
>
> So, if one is interested in multiplying large, dense univariate
> polynomials in Mathematica, the fastest approach is to use ListConvolve.
All this is true but the essential question -- one that David Harvey
alluded to in his original post -- is 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.
In other words if a computation involves multiplying large, dense
univariate polynomials then _internally_ Mathematica should use
ListConvolve. Now, given two polynomials, it takes time to check that
each _is_ a polynomial,
PolynomialQ[p1, x]; // Timing
PolynomialQ[p2, x]; // Timing
time to extract the coefficients,
c1 = CoefficientList[p1, x]; // Timing
c2 = CoefficientList[p2, x]; // Timing
time to multiplication using ListConvolve:
c = ListConvolve[c1, c2, {1, -1}, 0]; // Timing
and time to reconstruct the resulting polynomial
p = x^Range[0, Length[c] - 1] . c; // Timing
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?
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: Limit and Root Objects**
Next by Date:
**Re: FullSimplify and HypergeometricPFQ**
Previous by thread:
**Re: speed of multiplying polynomials**
Next by thread:
**Re: speed of multiplying polynomials**
| |