In our previous article we described a packed representation for sparse polynomials is designed for scalability and high performance. The expand and divide commands in Maple 14 use this representation internally to multiply and divide polynomials with integer coefficients, converting to and from Maple's generic data structure described here. In this post I want to show you how these algorithms work and why they are fast. It's a critical stepping stone for our next topic, which is parallelization.

Our first article introduced Maple's polynomial data structure and explained how Maple spends a lot of time working with monomials. To multiply polynomials having n and m terms, Maple must construct, simplify, hash, and sort all nm pairwise products to determine what monomials are equal. This work is performed even if the result has far fewer than nm terms, making it a rather inefficient way to multiply large multivariate polynomials. This article describes a new data structure for multivariate polynomials that is being added to Maple for a future release.

9xyz  -  4yz  -  6xyz  -  8x  -  5

This is the first in a series of short informal articles about our efforts to speed up polynomial arithmetic in Maple. We begin with an example of how polynomials are represented in Maple right now.

9xyz  -  4yz  -  6xyz  -  8x  -  5

When you enter a polynomial in Maple, it creates a generic data structure like the one above. In Maple's representation this polynomial is a sum of terms that is 11 words of memory long where each word is either 32 or 64 bits. For each term it stores a pointer to a monomial followed by a coefficient.

If you're writing an external library to be called from Maple, then you have the following problem. The user wants to interrupt your code. They are valiantly pressing control-C or the stop button in the Maple GUI, as your code grinds their machine to a halt. What do you do ?

Suppose you want to solve a large dense linear system AX=B over the rationals - what should you do? Well, one thing you should probably not do is directly apply Gaussian elimination. It does O(n^3) arithmetic operations, but the size of the numbers blow up, leading to an exponential bit complexity. Don't believe me? Try it:

with(LinearAlgebra):
for N from 5 to 9 do
  A := RandomMatrix(2^N, 2^N+1,generator=-10^5..10^5):
  TIMER := time(GaussianElimination(A...