Monomial order

also: lex, grlex, grevlex

A total order on monomials compatible with multiplication, which is what makes a leading term well defined. Lexicographic order sorts by the first variable that differs, graded orders compare total degree first, and the choice changes the cost of a Groebner basis computation by orders of magnitude.

A monomial order is a total order on monomials that is compatible with multiplication and well founded:

α ≺ β ⟹ α + γ ≺ β + γ, and ≺ has no infinite descending chain

The first condition makes a leading term meaningful under multiplication; the second is what makes division algorithms terminate. Three are standard, and they differ only in how ties are broken:

On x^2 and y^3, with x before y.

lex        first exponent that differs       x^2 > y^3
grlex      total degree, then lex            y^3 > x^2  (3 > 2)
grevlex    total degree, then the LAST       y^3 > x^2
           differing exponent, smaller wins

Lex is what elimination wants: a Groebner basis in lex order contains a polynomial in the last variable alone, which is what solves a system. Grevlex is what speed wants: for the same input it typically produces far smaller intermediate bases, often by orders of magnitude.

The usual strategy is to compute in grevlex and then convert, with FGLM or a Groebner walk, rather than compute in lex directly.

referenced by

Groebner basis

Building a CAS in OCaml Part 3Sparse multivariate polynomials, pseudo-division, the subresultant PRS against a modular GCD that is a thousand times faster, resultants, and a parser to drive it all.