Multivariate polynomials.

Let R be a ring and X = {x₁,..., x_n} 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[x₁,..., x_n-1][x_n].

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  =  a₁m₁ + ^... + a_pm_p. (35)

  
  
  where the m_i are pairwise different monomials and the a_i are nonzero coefficients, can be represented as an aggregate of terms [a_i, m_i].
• 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 < ^... < z^{n ...} < y < yz < ^... < yz^{n ...} < y² < y²z < ^... < y²z^{n ...} (36)

    
    

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

    1 < z < y < x < z² < zy < y² < zx < xy < x² < ^... < (37)