Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.symbolic.independent

Topic: New fast polynomial multiplication in Fermat
Replies: 4   Last Post: Nov 12, 2013 12:31 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Robert Lewis

Posts: 43
Registered: 7/17/08
New fast polynomial multiplication in Fermat
Posted: Oct 31, 2013 2:04 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.