Next: What are our requirements for Up: How to encode the elements Previous: Univariate polynomials.

### Multivariate polynomials.

Let R be a ring and X = {x1,..., xn} be a finite set of variables. The multivariate polynomial ring R[X] can be implemented in different ways.

RECURSIVELY.

• If n = 1 we can use a univariate representation
• otherwise we can view R[X] as a univariate polynomial ring with a multivariate polynomial ring as coefficient ring, say for instance R[x1,..., xn-1][xn].
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 R).
• Then the polynomial

 p  =  a1m1 + ... + apmp. (35)

where the mi are pairwise different monomials and the ai are nonzero coefficients, can be represented as an aggregate of terms [ai, mi].
• 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 X = {x > y > z} we have

 1 < z < ... < zn ... < y < yz < ... < yzn ... < y2 < y2z < ... < y2zn ... (36)

• The degree-lexicographical ordering. With X = {x > y > z} we have

 1 < z < y < x < z2 < zy < y2 < zx < xy < x2 < ... < (37)

Next: What are our requirements for Up: How to encode the elements Previous: Univariate polynomials.
Marc Moreno Maza
2003-06-06