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
- References:
- speed of multiplying polynomials
- From: dmharvey@math.harvard.edu
- speed of multiplying polynomials