MathGroup Archive 2007

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

Search the Archive

Re: speed of multiplying polynomials


dmharvey at math.harvard.edu wrote:
> 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?

The speed will depend heavily on the representation of the polynomials and
the algorithms used.  If Mathematica is using a sparse representation
then any algorithm will be at least O(d^2).  I know another system
that uses a uses a dense representation for univariate polynomials,
with Karatsuba and FFT multiplication.  These methods are an order of
magnitude faster if your polynomials are dense.


  • Prev by Date: Re: speed of multiplying polynomials
  • Next by Date: Re: A pattern matching problem
  • Previous by thread: Re: speed of multiplying polynomials
  • Next by thread: Re: speed of multiplying polynomials