MathGroup Archive 2007

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

Search the Archive

Re: speed of multiplying polynomials

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72651] Re: speed of multiplying polynomials
  • From: dmharvey at math.harvard.edu
  • Date: Sat, 13 Jan 2007 05:14:18 -0500 (EST)
  • References: <200701070439.XAA14676@smc.vnet.net><ent4s4$etq$1@smc.vnet.net>

Paul Abbott wrote:
> 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.

Exactly, thanks Paul.

Actually, there is another issue. I have tried ListConvolve for a few
cases, and compared its performance to polynomial multiplication in
certain other computer algebra systems.

For large degree, small coefficient problems (say degree 10000,
coefficients in [0, 1000]), Mathematica is definitely in the same ball
park, maybe still a little slower, but not hugely slower.

But for small degree, larger coefficients (say degree 100, coefficients
in [0, 10^500]), Mathematica was something like 20 times slower.

Is ListConvolve really the best Mathematica can do? I mean, if someone
really desperately needs to multiply polynomials in Mathematica, I find
it difficult to believe that the best they can do is still twenty times
slower than other systems. Of course they could go out and write the
multiplication code in C or something themselves, but that's missing
the point :-)

David


  • Prev by Date: On AspectRatio
  • Next by Date: Re: Integration using mathematica
  • Previous by thread: Re: speed of multiplying polynomials
  • Next by thread: Re: speed of multiplying polynomials