Polynomials are represented in APU using a sparse recursive data structure as shown in Figure 5.1. A polynomial has a field element and a term list. A polynomial can either be a terminal polynomial (that is, one representing a numerical coefficient) in which case the field element will contain the numerical value (of the desired type) and its term list will be empty. Or it can be a non-terminal polynomial in which case the field element will be of type Variable and the term list will point to a collection of term nodes, each of which will have a degree and a coefficient polynomial.
The variables over which the polynomial is defined are
stored in a linked list and it is assumed that in the sparse
recursive formulation the variables will appear in the order
the are stored in the linked list. (E.g. in Figure 5.1 the
ordering of the variables is assumed to be followed by
.)