The Math Forum

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

Advanced Search

Back to Topic List Back to Topic List  
Roman Pearce

Posts: 121
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
should be called "Johnson's algorithm". See

We've made contributions to improve it, but our actual work has
to improve the complexity of division and to do parallel algorithms.

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
multiplication. It's important to have the chaining optimization
this reduces the complexity to O(n^2) in the dense

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
anyone doing an implementation. It's also useful to compare against.

Maple 14 has the parallel version:

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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.