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

Re: speed of multiplying polynomials

• To: mathgroup at smc.vnet.net
• Subject: [mg72559] Re: speed of multiplying polynomials
• From: "Roman Pearce" <rpearcea at gmail.com>
• Date: Mon, 8 Jan 2007 05:04:39 -0500 (EST)

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.