Univariate polynomials.

Let $R$ be a ring. The univariate polynomial ring $R[x]$ can be implemented using different data types.

Expression trees.

All arithmetic operations are in ${\cal O}(1)$ . But the representation is not canonical: two different expression trees can encode the same polynomial. Therefore operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in ${\cal O}(n)$ where $n$ is the degree of the polynomial. Even worst the equality-test is ${\cal O}(n^2)$ (for non-balanced trees).

Arrays of coefficients.

The polynomial

$$p(x) \ \ = \ \ a_n x^n + \cdots + a_1 x + a_0$$ (34)

is coded by a record consisting of

• a single integer $s$ ,
• a single integer $d \leq s + 1$ ,
• an array of size $s$ such that $a_0+...+a_n x^n$ is represented by $[a_0,...,a_n,...]$ and $d = n$ .

This representation is said dense becasue all $a_i$ are coded, even those which are null. This representation is canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in ${\cal O}(1)$ . Addition and equality-test are in ${\cal O}(n)$ and multiplication is in ${\cal O}(n^2)$ . This representation is especially good when the ring of coefficients is a small prime field, i.e. ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ with $p$ prime and in the range $[2, 2^{N} - 1]$ .

List of terms.

The polynomial

$$p(x) \ \ = \ \ a_n x^n + \cdots + a_1 x + a_0$$ (35)

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