A term is internally represented as an integer vector whose components are exponents with respect to variables. A variable list specifies the correspondences between variables and components. A type of term ordering specifies a total order for integer vectors. A type of term ordering is represented by an integer, a list of integer or matrices.
There are following three fundamental types.
0 (DegRevLex; total degree reverse lexicographic ordering)
1 (DegLex; total degree lexicographic ordering)
DegRevLexordering, the result, in general, cannot directly be used for solving polynomial equations. It is used, however, in such a way that a Groebner basis is computed in this ordering after homogenization to obtain the final lexicographic Groebner basis.
2 (Lex; lexicographic ordering)
hgr()may be quite effective.
By combining these fundamental orderingl into a list, one can make various term ordering called elimination orderings.
In this example
Oi indicates 0, 1 or 2 and
the number of variables subject to the correspoinding orderings.
This specification means the following.
The variable list is separated into sub lists from left to right where
i-th list contains
Li members and it corresponds to
the ordering of type
Oi. The result of a comparison is equal
to that for the leftmost different sub components. This type of ordering
is called an elimination ordering.
Furthermore one can specify a term ordering by a matix.
Suppose that a real
M has the
Mv=0is equivalent to
vthe first non-zero component of
Then we can define a term ordering such that, for two vectors
t>s means that the first non-zero component
M(t-s) is non-negative.
Types of term orderings are used as arguments of functions such as
gr(). It is also set internally by
dp_ord() and is used
during executions of various functions.
For concrete definitions of term ordering and more information
about Groebner basis, refer to, for example, the book
Note that the variable ordering have strong effects on the computation time as well as the choice of types of term orderings.
 B=[x^10-t,x^8-z,x^31-x^6-x-y]$  gr(B,[x,y,z,t],2); [x^2-2*y^7+(-41*t^2-13*t-1)*y^2+(2*t^17-12*t^14+42*t^12+30*t^11-168*t^9 -40*t^8+70*t^7+252*t^6+30*t^5-140*t^4-168*t^3+2*t^2-12*t+16)*z^2*y +(-12*t^16+72*t^13-28*t^11-180*t^10+112*t^8+240*t^7+28*t^6-127*t^5 -167*t^4-55*t^3+30*t^2+58*t-15)*z^4, (y+t^2*z^2)*x+y^7+(20*t^2+6*t+1)*y^2+(-t^17+6*t^14-21*t^12-15*t^11+84*t^9 +20*t^8-35*t^7-126*t^6-15*t^5+70*t^4+84*t^3-t^2+5*t-9)*z^2*y+(6*t^16-36*t^13 +14*t^11+90*t^10-56*t^8-120*t^7-14*t^6+64*t^5+84*t^4+27*t^3-16*t^2-30*t+7)*z^4, (t^3-1)*x-y^6+(-6*t^13+24*t^10-20*t^8-36*t^7+40*t^5+24*t^4-6*t^3-20*t^2-6*t-1)*y +(t^17-6*t^14+9*t^12+15*t^11-36*t^9-20*t^8-5*t^7+54*t^6+15*t^5+10*t^4-36*t^3 -11*t^2-5*t+9)*z^2, -y^8-8*t*y^3+16*z^2*y^2+(-8*t^16+48*t^13-56*t^11-120*t^10+224*t^8+160*t^7 -56*t^6-336*t^5-112*t^4+112*t^3+224*t^2+24*t-56)*z^4*y+(t^24-8*t^21+20*t^19 +28*t^18-120*t^16-56*t^15+14*t^14+300*t^13+70*t^12-56*t^11-400*t^10-84*t^9 +84*t^8+268*t^7+84*t^6-56*t^5-63*t^4-36*t^3+46*t^2-12*t+1)*z, 2*t*y^5+z*y^2+(-2*t^11+8*t^8-20*t^6-12*t^5+40*t^3+8*t^2-10*t-20)*z^3*y+8*t^14 -32*t^11+48*t^8-t^7-32*t^5-6*t^4+9*t^2-t, -z*y^3+(t^7-2*t^4+3*t^2+t)*y+(-2*t^6+4*t^3+2*t-2)*z^2, 2*t^2*y^3+z^2*y^2+(-2*t^5+4*t^2-6)*z^4*y+(4*t^8-t^7-8*t^5+2*t^4-4*t^3+5*t^2-t)*z, z^3*y^2+2*t^3*y+(-t^7+2*t^4+t^2-t)*z^2, -t*z*y^2-2*z^3*y+t^8-2*t^5-t^3+t^2, -t^3*y^2-2*t^2*z^2*y+(t^6-2*t^3-t+1)*z^4, z^5-t^4]  gr(B,[t,z,y,x],2); [x^10-t,x^8-z,x^31-x^6-x-y]
As you see in the above example, the Groebner base under variable
[x,y,z,t] has a lot of bases and each base itself is
large. Under variable ordering
is already the Groebner basis.
Roughly speaking, to obtain a Groebner base under the lexicographic
ordering is to express the variables on the left (having higher order)
in terms of variables on the right (having lower order).
In the example, variables
y are already
expressed by variable
x, and the above explanation justifies
such a drastic experimental results.
In practice, however, optimum ordering for variables may not known
beforehand, and some heuristic trial may be inevitable.
Go to the first, previous, next, last section, table of contents.