Monomial orders for multivariate polynomials - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Groebner/MonomialOrders

Monomial orders for multivariate polynomials

 Calling Sequence Basis(J, tord) NormalForm(f, J, tord) LeadingTerm(f, tord)

Parameters

 J - a list or set of polynomials or a PolynomialIdeal tord - one of the monomial orders described below f - a polynomial

Description

 • A monomial order is a function for ordering the terms of multivariate polynomials. The commands in the Groebner package use monomial orders to define multivariate division, where the leading term of a polynomial is cancelled repeatedly using the leading terms of a set of polynomials. This leads naturally to the idea of a Groebner basis, where the multivariate division process produces a canonical remainder or normal form.
 • To ensure termination, a monomial order < should satisfy the following three properties:
 – It must be a total ordering of all the monomials of the polynomial ring.
 – It must be a well-ordering, that is, every set of monomials must have a least element.
 – If U, V, and W are monomials and U < V, then W*U < W*V.
 • These properties are satisfied by the following orders which are built in to Maple:
 – plex(x,...,x[n]) pure lexicographic order with x > x > ... > x[n]. This order is used to eliminate variables and solve systems of polynomial equations, however the resulting Groebner bases can be huge. Monomials are compared first by their degree in x, with ties broken by degree in x, etc.
 – grlex(x,...,x[n]) graded lexicographic order with x > x > ... > x[n]. Monomials are compared first by their total degree (see degree), with ties broken by lexicographic order. This order is not used very often because "tdeg" tends to be faster.
 – tdeg(x,...,x[n]) graded reverse lexicographic order (also called "grevlex" in the literature). Monomials are compared first by their total degree, with ties broken by reverse lexicographic order, that is, by smallest degree in x[n], x[n-1], etc. This order is commonly used because it typically provides for the fastest Groebner basis computations.
 – lexdeg(L,...,L[k]) is an elimination order.  The L[i] must be disjoint lists of variables. The variables in L[i] are eliminated from the subsequent variables for all i=1..k-1. This order is often used to eliminate variables when one does not want to compute an entire "plex" basis. It is equivalent to a product order that uses "tdeg" on each L[i].
 – wdeg(W,V) is a weighted-degree order.  V is a list of variables and W is a list of positive rational weights. Monomials are compared by their weighted degree, where each power of V[i] contributes W[i] to the degree of a term. Ties are broken by reverse lexicographic order.
 – 'matrix'(M,V) is a matrix order, where V is a list of variables and M is a list of lists of rational weights. In order to satisfy the three properties above, the first non-zero entry in each column of M must be positive. Monomials are compared by their weighted degree with respect to the first row of M, followed by the second row, etc. If the rank of M is less than the number of variables, ties are broken by reverse lexicographic order. To use matrix orders you must enclose the word matrix in single quotes, to avoid calling Maple's matrix constructor.
 – prod(t1,t2,...,tk) denotes a product order where the ti are monomial orders.  Monomials are compared first using t1, with ties broken by t2, etc.
 • In addition to the orders above Maple supports "reverse variants", where a monomial u is greater than v in the reverse order if and only if v > u in the original order. These orders typically do not satisfy the three properties of a monomial order, so computations using these orders may not terminate (unless the polynomials are homogeneous). These orders can be specified by appending the suffix "_min" to an order above (with the exception of prod orders). For example, plex_min(x,y,z) is the reverse of plex(x,y,z).
 • All of the monomial orders on this help page, including the reverse variants, are of type ShortMonomialOrder.
 • The Groebner package also allows user-defined monomial orders, which are specified by a procedure. To use them one must construct a MonomialOrder using the MonomialOrder command, see its help page for details. Be aware that some algorithms (such as the Groebner walk) do not support user-defined monomial orders. If possible, you should express your order in terms of the builtin orders above.

Examples

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $f≔5{x}^{3}y+{x}^{2}{w}^{2}t+5{x}^{3}yzt-2xz{w}^{3}t+3{y}^{2}{w}^{3}t$
 ${f}{≔}{-}{2}{}{t}{}{{w}}^{{3}}{}{x}{}{z}{+}{3}{}{t}{}{{w}}^{{3}}{}{{y}}^{{2}}{+}{5}{}{t}{}{{x}}^{{3}}{}{y}{}{z}{+}{t}{}{{w}}^{{2}}{}{{x}}^{{2}}{+}{5}{}{{x}}^{{3}}{}{y}$ (1)

We first consider lexicographic order with x > y > z > w > t. The terms of f can be ordered by Maple's sort command.

 > $\mathrm{sort}\left(f,\left[x,y,z,w,t\right],\mathrm{plex}\right)$
 ${5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}{+}{5}{}{{x}}^{{3}}{}{y}{+}{{x}}^{{2}}{}{{w}}^{{2}}{}{t}{-}{2}{}{x}{}{z}{}{{w}}^{{3}}{}{t}{+}{3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}$ (2)

The LeadingTerm command returns the sequence (leading monomial, leading coefficient). To construct the actual term we multiply its output using *.

 > $\mathrm{*}\left(\mathrm{LeadingTerm}\left(f,\mathrm{plex}\left(x,y,z,w,t\right)\right)\right)$
 ${5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}$ (3)

There are two ways of computing the smallest term with respect to a monomial order. One is to use the "reverse variant" and compute the leading term.  We can also use the TrailingTerm command.

 > $\mathrm{*}\left(\mathrm{TrailingTerm}\left(f,\mathrm{plex}\left(x,y,z,w,t\right)\right)\right)$
 ${3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}$ (4)
 > $\mathrm{*}\left(\mathrm{LeadingTerm}\left(f,\mathrm{plex_min}\left(x,y,z,w,t\right)\right)\right)$
 ${3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}$ (5)

Next we consider graded lexicographic order with x > y > z > w > t. Terms are compared first by their total degree, with ties broken by lexicographic order. This is the default order for Maple's sort command.

 > $\mathrm{sort}\left(f,\left[x,y,z,w,t\right]\right)$
 ${5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}{-}{2}{}{x}{}{z}{}{{w}}^{{3}}{}{t}{+}{3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}{+}{{x}}^{{2}}{}{{w}}^{{2}}{}{t}{+}{5}{}{{x}}^{{3}}{}{y}$ (6)
 > $\mathrm{*}\left(\mathrm{LeadingTerm}\left(f,\mathrm{grlex}\left(x,y,z,w,t\right)\right)\right)$
 ${5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}$ (7)
 > $\mathrm{*}\left(\mathrm{TrailingTerm}\left(f,\mathrm{grlex}\left(x,y,z,w,t\right)\right)\right)$
 ${5}{}{{x}}^{{3}}{}{y}$ (8)

We can examine the terms of maximal degree using the InitialForm command. All but two terms have total degree 6.

 > $\mathrm{initf}≔\mathrm{InitialForm}\left(f,\mathrm{grlex}\left(x,y,z,w,t\right)\right)$
 ${\mathrm{initf}}{≔}{-}{2}{}{x}{}{z}{}{{w}}^{{3}}{}{t}{+}{3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}{+}{5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}$ (9)
 > $f-\mathrm{initf}$
 ${{x}}^{{2}}{}{{w}}^{{2}}{}{t}{+}{5}{}{{x}}^{{3}}{}{y}$ (10)

Here are the terms of f sorted in (ascending) graded-reverse lexicographic order. Among the last three terms, ties are broken by smallest degree in t, then w, and finally z before the order of the monomials is determined.

 > $\mathrm{sort}\left(\left[\mathrm{op}\left(f\right)\right],\left(a,b\right)→\mathrm{TestOrder}\left(a,b,\mathrm{tdeg}\left(x,y,z,w,t\right)\right)\right)$
 $\left[{5}{}{{x}}^{{3}}{}{y}{,}{{x}}^{{2}}{}{{w}}^{{2}}{}{t}{,}{-}{2}{}{x}{}{z}{}{{w}}^{{3}}{}{t}{,}{3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}{,}{5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}\right]$ (11)

In the elimination order below, we compare monomials first using tdeg(x,y) with ties broken by tdeg(z,w,t).  In a Groebner basis computation using this order, the variables {x,y} would be eliminated as much as possible from the polynomial system.

 > $\mathrm{sort}\left(\left[\mathrm{op}\left(f\right)\right],\left(a,b\right)→\mathrm{TestOrder}\left(a,b,\mathrm{lexdeg}\left(\left[x,y\right],\left[z,w,t\right]\right)\right)\right)$
 $\left[{-}{2}{}{x}{}{z}{}{{w}}^{{3}}{}{t}{,}{3}{}{{y}}^{{2}}{}{{w}}^{{3}}{}{t}{,}{{x}}^{{2}}{}{{w}}^{{2}}{}{t}{,}{5}{}{{x}}^{{3}}{}{y}{,}{5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}\right]$ (12)

Next we consider a weighted degree order.  Each power of x counts for two, while each power of y counts for one half. The remaining variables count for one.

 > $\mathrm{*}\left(\mathrm{LeadingTerm}\left(f,\mathrm{wdeg}\left(\left[2,\frac{1}{2},1,1,1\right],\left[x,y,z,w,t\right]\right)\right)\right)$
 ${5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}$ (13)
 > $\mathrm{WeightedDegree}\left(f,\left[2,\frac{1}{2},1,1,1\right],\left[x,y,z,w,t\right]\right)$
 $\frac{{17}}{{2}}$ (14)

All of the builtin orders have representations as matrix orders. We will represent graded reverse lexicographic order as a matrix order and compute the leading term of f.

 > $M≔\mathrm{MatrixOrder}\left(\mathrm{tdeg}\left(x,y,z,w,t\right),\left[x,y,z,w,t\right]\right)$
 ${M}{≔}\left[\left[{1}{,}{1}{,}{1}{,}{1}{,}{1}\right]{,}\left[{0}{,}{0}{,}{0}{,}{0}{,}{-1}\right]{,}\left[{0}{,}{0}{,}{0}{,}{-1}{,}{0}\right]{,}\left[{0}{,}{0}{,}{-1}{,}{0}{,}{0}\right]{,}\left[{0}{,}{-1}{,}{0}{,}{0}{,}{0}\right]\right]$ (15)
 > $\mathrm{Matrix}\left(M\right)$
 $\left[\begin{array}{ccccc}{1}& {1}& {1}& {1}& {1}\\ {0}& {0}& {0}& {0}& {-1}\\ {0}& {0}& {0}& {-1}& {0}\\ {0}& {0}& {-1}& {0}& {0}\\ {0}& {-1}& {0}& {0}& {0}\end{array}\right]$ (16)
 > $\mathrm{*}\left(\mathrm{LeadingTerm}\left(f,'\mathrm{matrix}'\left(M,\left[x,y,z,w,t\right]\right)\right)\right)$
 ${5}{}{{x}}^{{3}}{}{y}{}{z}{}{t}$ (17)

For examples of multivariate polynomial division see Groebner[NormalForm]. To compute Groebner bases, use the Groebner[Basis] command. To define monomial orders other than the ones on this page, see Groebner[MonomialOrder].