### Multivariate polynomials.

Let be a ring and be a finite set of variables. The multivariate polynomial ring can be implemented in different ways.

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 .
This implies to choose an ordering on the variables and a representation for univariate polynomials.

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)

Marc Moreno Maza
2008-01-07