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.

The monomials themselves are separate Maple objects. They use a different type of header called a prod, short for product of powers. In this case the prods have the variables {x,y,z} raised to different powers, which you can see by using the dismantle command below.

dismantle( 9*x*y^3*z - 4*y^3*z^2 - 6*x*y^2*z - 8*x^3 - 5 );

SUM(11)
   PROD(7)
      NAME(4): x
      INTPOS(2): 1
      NAME(4): y
      INTPOS(2): 3
      NAME(4): z
      INTPOS(2): 1
   INTPOS(2): 9
   PROD(5)
      NAME(4): y
      INTPOS(2): 3
      NAME(4): z
      INTPOS(2): 2
   INTNEG(2): -4
   PROD(7)
      NAME(4): x
      INTPOS(2): 1
      NAME(4): y
      INTPOS(2): 2
      NAME(4): z
      INTPOS(2): 1
   INTNEG(2): -6
   PROD(3)
      NAME(4): x
      INTPOS(2): 3
   INTNEG(2): -8
   INTNEG(2): -5
   INTPOS(2): 1

The design of Maple is generic, so almost any Maple data structure can appear in sums or prods. For example, the monomials in a sum could be functions such as sin(x), or the objects in a prod could be other sums. Maple automatically distributes sums of sums and combines prods of prods, but it does not multiply everything out automatically.

dismantle( 2*(x+1) + 3*(x-2) );      # simplified to 5*x-4

dismantle( x*y*(x^2*y*z) );          # simplified to x^3*y^2*z

dismantle( x*(y-1) + (x+1)*(y+1) );  # not expanded automatically

expand( x*(y-1) + (x+1)*(y+1) );     # computes 2*x*y + y + 1

Maple recognizes identical objects by their address in memory. It maintains a hash table of every object in the system, called the simplification table, and when a new object is created it is simplified recursively, flattened, hashed, and either added to the table or discarded and replaced by a pre-existing copy.

As a result of this design, monomials almost never need to be compared directly. Consider a polynomial multiplication (5x + y - 2) ⋅ (2 y - x + 1). Maple constructs a big sum of all the pairwise products:

10xy - 5xx + 5x + 2yy - xy + y - 4y + 2x - 2

The products are simplified and the sum is sorted by address of monomial:

10xy - xy - 5x + 2y + 5x + 2x + y - 4y - 2

And finally like terms are merged in a single pass:

9xy - 5x + 2y + 7x - 3y - 2

For moderately sized problems this approach works well, and it's hard to fault Maple's design. For larger problems it can be wasteful to use O(nm) memory to multiply n × m terms, so Maple switches to a divide and conquer approach. However the system will construct, simplify, and hash all nm products of terms. Unless the coefficients are very large, these operations take the vast majority of the total time.