**RECURSIVELY. **

- If we can use a univariate representation
- otherwise we can view as a univariate polynomial ring with a multivariate polynomial ring as coefficient ring, say for instance .

*
*

*
*

**AS LINEAR COMBINATIONS OF MONOMIALS. **

- By
*monomial*we mean any product of variables. - The product of variable is assumed to be commutative and induces a commutative multiplication for monomials.
- Each polynomial can be viewed as a linear combination of monomials (with coefficients in ).
- Then the polynomial
(36)

where the are pairwise different monomials and the are nonzero coefficients, can be represented as an aggregate of terms . - This provides us with a canonical representation.
- To have a fast equality-test, the aggregate of terms
must be
*linear*. In other words, there should be a*first*term, a*second*term, ... Thus this aggregate should better be a*list*or an*array*and the monomials should be totally ordered. - Two types of monomial orderings are frequently used.
- The lexicographical ordering. With
we have
(37)

- The degree-lexicographical ordering. With
we have
(38)

- The lexicographical ordering. With
we have

*
*

2008-01-07