Monomial order

From Wikipedia, the free encyclopedia

In mathematics, a monomial order is a total order on the set of all monomials (considering monomials which only differ in their coefficient to be the same) satisfying two additional properties.

  1. If u < v and w is any other monomial, then uw<vw. In other words, the ordering respects multiplication.
  2. The ordering is a well ordering

Most monomial orders impose an ordering on the indeterminates, but differ in their exact details. Some important examples of monomial orders include:

  • Lexicographic order (lex) orders according to the highest power of the most significant indeterminate, using less significant indeterminates to break ties.
  • Reverse lexicographic order (revlex) orders according to the lowest power of the least significant indeterminate, using more significant indeterminates to break ties.
  • Graded lexicographic order (grlex) orders by total degree first, then breaks ties using lexicographic order.
  • Graded reverse lexicographic order (grevlex) orders by total degree first, then breaks ties using reverse lexicographic order.
  • An elimination order guarantees that a monomial involving any of a set of indeterminates will always be greater than a monomial not involving any of them.
  • A product order orders one set of indeterminates using one monomial order, then breaks ties using a different order on a second set.
  • Weight orders treat the powers of indeterminates as a vector and orders according to the dot product with a weight vector.

All monomial orders can be constructed as product orders of weight orders (Cox et al. pp. 74-75)

For example, consider the monomials xy2z, z2, x3, and x2z2. Using the indeterminate order x > y > z, here's how some of the monomial orders above would order these four monomials:

  • Lex: x3 > x2z2 > xy2z > z2 (power of x dominates)
  • Grlex: x2z2 > xy2z > x3 > z2 (total degree dominates; higher power of x broke tie)
  • Grevlex: xy2z > x2z2 > x3 > z2 (total degree dominates; lower power of z broke tie)

Monomial orderings are most commonly used with Groebner bases and multivariate division, and different orders can led to different results. For example, grevlex has a reputation for producing relatively small Groebner bases, while elimination orders can be used with the same algorithms to solve systems of polynomial equations by eliminating variables.

More generally you can also allow orderings which do not satisfy condition 2. Orderings satisfying 2 are called global orderings. Being a global ordering is equivalent, for polynomial rings in finitely many variables, to the property that all variables xi are greater than 1.

Orderings with the contrary property, that all variables xi are smaller than 1, are called local orderings. Orderings which are neither global nor local are called mixed orderings.

[edit] References

* David Cox, John Little, and Donal O'Shea (2007). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer. ISBN 0-387-35650-9