Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math.symbolic
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
New fast polynomial multiplication in Fermat
Replies:
4
Last Post:
Nov 12, 2013 12:31 AM




New fast polynomial multiplication in Fermat
Posted:
Oct 31, 2013 2:04 PM


New 64 bit versions, Fermat 5.0, have been posted that implement a fast multivariate polynomial multiplication algorithm.
Though this way of multiplying polynomials actually has a long history, I am indebted to Michael Monagan of Simon Fraser University for bringing it to my attention at the 2013 ECCAD conference in Maryland. He has described the idea in a preprint http://www.cecm.sfu.ca/~monaganm/papers/ASCM13.pdf
Basically, the idea is to store each term, or monomial, of a multivariate polynomial in a single node instead of storing the polynomial as a recursive structure of nodes at one level pointing to nodes at lower levels. Remarkable speedups are possible, 30%  84% in real problems involving 6  18 polynomial variables. More details are here:
http://home.bway.net/lewis/fer64mono.html
The 64 bit versions for Mac and Linux are available here:
http://home.bway.net/lewis/fer64.html
Robert H. Lewis Fordham University



