[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.
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
