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)
DegRevLex
ordering, 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)
gr()
and/or hgr()
may be quite effective.
By combining these fundamental orderingl into a list, one can make various term ordering called elimination orderings.
[[O1,L1],[O2,L2],...]
In this example Oi
indicates 0, 1 or 2 and Li
indicates
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
the 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 n
, m
matrix M
has the
following properties.
v
of length m
Mv=0
is equivalent
to v=0
.
v
the first non-zero component
of Mv
is non-negative.
Then we can define a term ordering such that, for two vectors
t
, s
, t>s
means that the first non-zero component
of 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
[Becker,Weispfenning]
.
Note that the variable ordering have strong effects on the computation time as well as the choice of types of term orderings.
[90] B=[x^10-t,x^8-z,x^31-x^6-x-y]$ [91] 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] [93] 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
ordering [x,y,z,t]
has a lot of bases and each base itself is
large. Under variable ordering [t,z,y,x]
, however, B
itself
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 t
, z
, and 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.