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.