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: Re: Multivariate polynomial multiplication over Z
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Roman Pearce

Posts: 120
Registered: 1/25/05
Re: Multivariate polynomial multiplication over Z
Posted: May 13, 2010 2:02 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Since this is turning into an all purpose post, I'm going to crosspost
to sci.math.symbolic. I want to start by saying that the heap
method
should be called "Johnson's algorithm". See
http://portal.acm.org/citation.cfm?id=1086847

We've made contributions to improve it, but our actual work has
been
to improve the complexity of division and to do parallel algorithms.
See http://www.cecm.sfu.ca/~rpearcea/

We're trying to popularize the approach because we think it's better,
and the benefit of doing these basic operations well spill over into
many other parts of computer algebra systems.

To that end, I put up some example code showing how we implemented
heap
multiplication. It's important to have the chaining optimization
since
this reduces the complexity to O(n^2) in the dense
case.
http://www.cecm.sfu.ca/~rpearcea/heapmul.zip

Also, the inevitable "is this open source" question is sure to pop up.
No, it's not. It's just an short example showing how we did it to
help
anyone doing an implementation. It's also useful to compare against.

Maple 14 has the parallel version:
http://www.mapleprimes.com/blog/romanpearce/parallelsparsepolynomialmultiplicationmaple14

As Richard Fateman points out, there are better ways of multiplying
polynomials so don't take this as the final word. Dense algorithms
are useful, and other sparse algorithms can win in some situations.
It may depend on the system and the implementation.

What I like about the algorithm is that it's fairly simple and it
gets you to a good division algorithm quickly. This is something
which can be a bigger problem since the naive algorithm that does
repeated subtractions can be O(n^3) with multivariate polynomials.
Other algorithms use O(n^2) memory. The heap is hard to beat.



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.