|
Let P be the polynomial ring R[x1, ..., xn] of rank n over a
ring R. A monomial (or power product) of P is a product of
powers of the variables (or indeterminates) of P, that is, an expression
of the form
x1e1 ... xnen with ei ≥0 for 1 ≤i ≤n.
Multivariate polynomials in Magma are stored efficiently in distributive
form, using arrays of coefficient-monomial pairs, where the coefficient
is in the base ring R. The word `term' will always refer to a
coefficient multiplied by a monomial.
Monomial orders are of critical importance when dealing with Gröbner
bases.
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 ∈M, s ≤t implies su ≤tu for all
s, t, u ∈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 Qn with non-negative entries
is called a weight vector
since it weights a monomial s by the product s.W (defined to be the
dot 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 [subsection Weight: weight]).
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 extra arguments 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.
See also [CLO96, Chap. 2, Para 2] for more details about the first
three orders.
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.
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.
This order is rarely used because the grevlex order below is usually
a better degree order (i.e., yields smaller Gröbner bases).
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.
Definition (given a sequence W of n positive integer weights):
s < t iff the total weighted degree ds of s w.r.t. W is less than the total degree
dt of t w.r.t. W or ds=dt 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 arguments ("grevlexw", W).
The order is called "graded reverse lexicographical (weighted)"
since it first grades the monomials by weighted degree w.r.t. W,
and then decides ties by the negation of the
lexicographical order applied to the variables in reverse order.
If W = [1, 1, ..., 1], then this order is equal to the grevlex
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.
This order is similar to the grevlex order, but is
useful if an ideal is homogeneous with respect to the grading
given by W, since the Gröbner basis of the ideal will tend to
be smaller with this order.
Definition (given k with 1 ≤k ≤n - 1):
s < t iff sk < tk with respect to the grevlex order or
sk = tk and sk' < tk' with respect to the grevlex order
where mk denotes the monomial consisting of the first k exponents of
m and mk' 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[x1, ..., xn] with respect to this order, then
G ∩K[xk + 1, ..., xn] is a Gröbner basis of the k-th
elimination ideal
I ∩K[xk + 1, ..., xn]. (It is usually easier to
compute a Gröbner basis with respect to this order for any k
than with respect to the full lexicographical 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.
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 sU < tU with respect to the grevlex order or
sU = tU and sV < tV with respect to the grevlex order
where mL 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.
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 sV < tV with respect to the grevlex order or
sV = tV and sU < tU 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
[BW93, p. 390] for the motivation for this order.
Definition (given i with 1 ≤i ≤n):
s < t iff sL < tL with respect to the grevlex order or
sL = tL 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 when monomials are compared,
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 a zero-dimensional 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.
Definition (given n weight vectors W1, ... Wn from Qn):
s < t iff there exists 1 ≤i ≤n such that
s.Wj = t.Wj for 1 ≤j < i and s.Wi < t.Wi.
The order is specified by the arguments ("weight", Q) where Q
is a sequence of n2 non-negative integers or rationals describing the n
weight vectors of length n (in row major order).
The n weight vectors must describe a vector space basis of Qn (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]
|