Let P be the polynomial ring R[x_1, ..., x_n] of rank n over a ring R. A monomial (or power product) of P is a product of powers of the variables of P, that is, an expression of the form x_1^(e_1) ... x_n^(e_n) with e_i >= 0 for 1 <= i <= n. Let M be the set of all monomials of P. A monomial ordering on M is a total order < on M such that 1 <= s for all s in M, s <= t implies su <= tu for all s, t, u in M, and M is a well-ordering (every non-empty subset of M possesses a minimal element w.r.t. <). Monomial orders can be naturally specified in terms of weight vectors: a vector W from Q^n with non-negative entries is called a weight vector since it weights a monomial s by the product s.W (defined to be the inner product of the exponent vector of s with W); any sequence of n linearly independent weight vectors determines a monomial order on M (see the weight order below). All monomial orderings can in fact be represented in terms of weight vectors.
Multivariate polynomial rings are constructed in Magma such that the monomials of any polynomial are sorted with respect to a specified monomial order (with the greatest monomial first). Gröbner basis computations are dramatically affected by the choice of monomial order. Magma provides an extensive choice of monomial orders. Currently, the intrinsic functions PolynomialRing (or PolynomialAlgebra), ChangeOrder and VariableExtension expect a monomial order; it is specified by a string giving the name, optionally followed by parameters for that order.
We now describe each of the monomial orders available in Magma. We suppose that s and t are monomials from P which has rank n. Any order on the monomials is then fully defined by just specifying exactly when s < t with respect to that order. In the following, the argument(s) are described for an order as a list of expressions; that means that the expressions (without the parentheses) should be appended to any base arguments when any particular intrinsic function is called which expects a monomial order.
Definition: s < t iff there exists 1 <= i <= n such that the first i - 1 exponents of s and t are equal but the i-th exponent of s is less than the i-th exponent of t. The order is specified by the argument ("lex").
The order is called "lexicographical" since it orders the monomials
as if they were words in a dictionary. The i-th
variable is greater than the (i + 1)-th variable for 1 <= i < n so
the first variable is the greatest variable.
A Gröbner basis of an ideal with respect to the lexicographical order usually
represents the most information about the ideal but can be hard to compute.
Graded Lexicographical: glex
Definition: s < t iff the total degree of s is less than the total degree of t or the total degree of s is equal to the total degree of t and s < t with respect to the lexicographical order. The order is specified by the argument ("glex").
The order is called "graded lexicographical" since it first grades the
monomials by total degree, and then decides ties by the lexicographical order.
The i-th variable is greater than the (i + 1)-th variable for 1 <= i < n
so the first variable is the greatest variable.
Graded Reverse Lexicographical: grevlex
Definition: s < t iff the total degree of s is less than the total degree of t or the total degree of s is equal to the total degree of t and s > t with respect to the lexicographical order applied to the exponents of s and t in reverse order. The order is specified by the argument ("grevlex").
The order is called "graded reverse lexicographical" since it first grades
the monomials by total degree, and then decides ties by the negation of the
lexicographical order applied to the variables in reverse order.
Again, the i-th variable is greater than the (i + 1)-th variable
for 1 <= i < n so the first variable is the greatest variable.
A Gröbner basis of an ideal with respect to the graded reverse
lexicographical order is usually the easiest to compute so it is recommended
that this order be used when just any Gröbner basis for an ideal is desired.
Elimination (k): elim
Definition (given k with 1 <= k <= n - 1): s < t iff s_k < t_k with respect to the grevlex order or s_k = t_k and s_(k') < t_(k') with respect to the grevlex order where m_k denotes the monomial consisting of the first k exponents of m and m_(k') denotes the monomial consisting of the last n - k exponents of m (this order is thus the concatenation of two block grevlex orders). The order is specified by the arguments ("elim", k).
The order is called "elimination" since the first k variables are
"eliminated". If G is a Gröbner basis of an ideal I of the polynomial
ring K[x_1, ..., x_n] with respect to this order, then
G intersect K[x_(k + 1), ..., x_n] is a Gröbner basis of the k-th
elimination ideal
I intersect K[x_(k + 1), ..., x_n].
Again, the i-th variable is greater than the (i + 1)-th variable
for 1 <= i < n so the first variable is the greatest variable.
Elimination List: elim
Definition (given sequences U and V such that U and V contain distinct integers in the range 1 to n and the sum of the lengths of U and V is n and U and V are disjoint): s < t iff s_U < t_U with respect to the grevlex order or s_U = t_U and s_V < t_V with respect to the grevlex order where m_L denotes the monomial consisting of the exponents of m corresponding to the entries of L in order. The order is specified by the arguments ("elim", U, V). V may be omitted if desired so the arguments are just ("elim", U); in this case V is chosen to be an appropriate sequence to complement U.
The order is called "elimination" since the variables in U are
"eliminated". The order of the elements in U and V are significant
since the ordering on the variables makes U[1] greatest, then U[2],
etc., then V[1], V[2], etc.
Inverse Block: invblock
Definition (given sequences U and V such that U and V contain distinct integers in the range 1 to n and the sum of the lengths of U and V is n and U and V are disjoint): s < t iff s_V < t_V with respect to the grevlex order or s_V = t_V and s_U < t_U with respect to the grevlex order. The order is specified by the arguments ("invblock", U, V). V may be omitted if desired so the arguments are just ("invblock", U); in this case V is chosen to be an appropriate sequence to complement U.
The order is called "inverse block" since it applies a block ordering
on the exponents on V then U which inverts the lists supplied to
the elimination list order. Thus this is the same as the elimination
order except that the lists U and V are swapped. See Becker &
Weispfenning, page 390, for the motivation for this order.
Univariate: univ
Definition (given i with 1 <= i <= n): s < t iff s_L < t_L with respect to the grevlex order or s_L = t_L and the i-th exponent of s is less than the i-th exponent of t, where L is the sequence [1 .. n] with i deleted. The order is specified by the arguments ("univ", i).
The order is called "univariate" since monomials are compared so that
any monomial not containing the i-th variable is greater than any
monomial containing the i-th variable.
Thus all variables but the i-th are "eliminated" so that
a Gröbner basis of an ideal I with this ordering will contain the
unique monic generator of the elimination ideal consisting of all
the polynomials in I containing the i-th variable alone.
The j-th variable is greater than the (j + 1)-th variable for 1 <= j < i
and i < j <= n and the j-th variable is greater than the i-th variable
for any j not= i.
Weight: weight
Definition (given n weight vectors W_1, ... W_n from Q^n): s < t iff there exists 1 <= i <= n such that s.W_j = t.W_j for 1 <= j < i and s.W_i < t.W_i. The order is specified by the arguments ("weight", Q) where Q is a sequence of n^2 non-negative integers or rationals describing the n weight vectors of length n (in row major order).
The n weight vectors must describe a basis of Q^n (i.e., be linearly independent), since otherwise this would not yield a total ordering on the monomials. The weight order allows one to specify any possible monomial order; any of the monomial orders mentioned above can be specified by an appropriate choice of weight vectors. However, using the in-built versions of the specialized orders above is much faster than constructing versions of them based on weight vectors. The next section contains an example in which a polynomial ring is constructed with a weight order for the monomials.
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]