monomial orderings

monomial orderings

We can make polynomial rings with various other orderings of the monomials used in storing and displaying the polynomials. The choice of ordering can make a difference in the time taken in various computations.

The material in this section will be completely redone soon.

The default is to use the graded reverse lexicographic ordering of monomials. This means that terms of higher total degree come first; and for two terms of the same degree, the term with the higher power of the last variable comes last; for terms with the same power of the last variable, the exponent on the next to last variable is consulted, and so on.

i1 : R=ZZ/101[a,b,c]



o1 = R



o1 : PolynomialRing

i2 : (a+b+c+1)^2



      2           2                  2

o2 = a  + 2a*b + b  + 2a*c + 2b*c + c  + 2a + 2b + 2c + 1



o2 : R

Explicit comparison of monomials with respect to the chosen ordering is possible.

i3 : b^2 > a*c



o3 = true

The comparison operator ? returns a symbol indicating the result of the comparison: the convention is that the larger monomials are printed first (leftmost).

i4 : b^2 ? a*c



o4 = >



o4 : Symbol

The monomial ordering is also used when sorting lists with sort.

i5 : sort {1_R, a, a^2, b, b^2, a*b, a^3, b^3}



       3   2           3   2

o5 = {b , b , a*b, b, a , a , a, 1}



o5 : List

The next ring uses MonomialOrder to specify reverse lexicographic ordering. This means that the term with the higher power of the last variable comes last; for terms with the same power of the last variable, the exponent on the next to last variable is consulted, and so on. Under this ordering the monomials are not well ordered.

i6 : R=ZZ/101[x,y,z,MonomialOrder=>RevLex];

We currently get a monomial overflow if we try to compute anything in this ring, sigh.

The next ring uses graded lexicographic ordering. This means that terms of higher total degree come first; for two terms of the same degree, the term with the higher power of the first variable comes first: for terms with the same power of the first variable the power of the second variable is consulted, and so on.

i7 : R=ZZ/101[a,b,c,MonomialOrder=>GLex];

i8 : (a+b+c+1)^2



      2                  2           2

o8 = a  + 2a*b + 2a*c + b  + 2b*c + c  + 2a + 2b + 2c + 1



o8 : R

(Notice how similar the result above is to the one obtained when graded reverse lexicographic ordering is used.)

The next ring uses lexicographic ordering. This means that terms with the highest power of the first variable come first: for two terms with the same power of the first variable the power of the second variable is consulted, and so on.

i9 : R=ZZ/101[a,b,c,MonomialOrder=>Lex];

i10 : (a+b+c+1)^2



       2                       2                2

o10 = a  + 2a*b + 2a*c + 2a + b  + 2b*c + 2b + c  + 2c + 1



o10 : R

The next ring uses an elimination order suitable for eliminating the first two variables, a and b. In such an ordering we want all terms in which either of the first two variables appears to come before all of those terms in which the first two variables don't appear. This particular ordering accomplishes this by consulting first the graded reverse lexicographic ordering ignoring all variables but the first two, and in case of a tie, consulting the graded reverse lexicographic ordering of the entire monomials.

i11 : R=ZZ/101[a,b,c,MonomialOrder=>Eliminate 2];

i12 : (a+b+c+1)^2



       2           2                            2

o12 = a  + 2a*b + b  + 2a*c + 2b*c + 2a + 2b + c  + 2c + 1



o12 : R

The next ring uses the product ordering that segregates the first variable from the next two. This means that terms come first that would come first in the graded reverse lexicographic ordering when their parts involving the second two variables are ignored, and in case of equality, the graded reverse lexicographic ordering of their parts involving just the next two variables is consulted.

i13 : R=ZZ/101[a,b,c,MonomialOrder=>ProductOrder{1,2}];

i14 : (a+b+c+1)^2



       2                       2           2

o14 = a  + 2a*b + 2a*c + 2a + b  + 2b*c + c  + 2b + 2c + 1



o14 : R

See MonomialOrder for further details.