### Univariate polynomials.

Let be a ring. The univariate polynomial ring can be implemented using different data types.

Expression trees.
All arithmetic operations are in . But the representation is not canonical: two different expression trees can encode the same polynomial. Therefore operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in where is the degree of the polynomial. Even worst the equality-test is (for non-balanced trees).
Arrays of coefficients.
The polynomial

 (34)

is coded by a record consisting of
• a single integer ,
• a single integer ,
• an array of size such that is represented by and .
This representation is said dense becasue all are coded, even those which are null. This representation is canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in . Addition and equality-test are in and multiplication is in . This representation is especially good when the ring of coefficients is a small prime field, i.e. with prime and in the range .
List of terms.
The polynomial

 (35)

is coded by the list of records where is a nonzero coefficient and such that is sorted decreasingly w.r.t. . This representation is said sparse, since only the nonzero are coded. This representation is also canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in . Moreover the operation REDUCTUM does not require coefficient duplication (on the contrary of the previous representation). Addition and equality-test are in and multiplication is in . This representation is especially good when the ring of coefficients is itself a ring of sparse polynomials.

Marc Moreno Maza
2008-01-07