The title of this paper describes the content exactly. Maple did not previously have a dedicated data structure for polynomials; it stored them as general expressions, which were stored in a sum of products (SoP) representation. Since there was no guarantee that terms would be stored in order, operations like degree involved traversing the entire data structure: n+1 vectors for a sum of n products. The process was, therefore, very cache unfriendly.

The new data structure only applies to polynomials for which bit-packing techniques--which reminded me of the algebra systems of the 1960s, allowing an entire monomial to be packed in a 64-bit integer--apply. Otherwise, the traditional Maple data structure is used, invisible to the programmer. Indeed, though the authors do not make the point explicitly, the destructuring command op, applied to these new structures, returns the same results it would have on the equivalent old structures. Indeed, the only way I know how to tell the difference is via the little documented (and not described in this paper) dismantle command.

The authors present some fairly impressive benchmarks, both for basic operations like degree and coefficient, and for polynomial multiplication and factorization. There are very substantial improvements in time over the old (Maple 13) system. Compared to Maple 16--which used similar algorithms internally, but converted to/from the traditional structure--multiplication and division are very similar on one core, but the new system is faster on four cores. For factorization, the new system is distinctly faster than Maple 16, and again shows better parallelism.

The paper states: “We are working to have the new data representation ready for Maple 17.” The authors succeeded; it is in Maple 17. I have to report that I do not seem to be seeing, in my applications, the same sort of speedup, but this is under investigation.