The Recursive Dense polynomial data structure

Michael Monagan, CECM, Simon Fraser Univeristy

Friday April 8th, 12:30pm, K9505.


The winner of the 2021 Jenks prize for software engineering excellence in computer algebra is Pari. Pari was designed for computing with polynomials over algebraic number fields. It is the only computer algebra system to use the "recursive dense" polynomial data structure as the default for representing multivariate polynomials and elements of number fields. Two older computer algebra systems, Macsyma and REDUCE use "recursive sparse" data structures. In contrast, most of the newer computer algebra systems, CoCoA, McCaulay2, Magma, Maple, Mathematica, and Singular, for example, all use "sparse distributed" data structures.

In this talk I will show the differences between these polynomial data structures and focus on the recursive dense data structure. Why did Pari choose it? I will then show Maple's RECDEN data structure which Maple uses when it computes with polynomials over algebraic number fields and give a demo of RECDEN.