| [ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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)In general, computation by this ordering shows the fastest speed in most Groebner basis computations. However, for the purpose to solve polynomial equations, this type of ordering is, in general, not so suitable. The Groebner bases obtained by this ordering is used for computing the number of solutions, solving ideal membership problem and seeds for conversion to other Groebner bases under different ordering.
1 (DegLex; total degree lexicographic ordering)By this type term ordering, Groebner bases are obtained fairly faster
than Lex (lexicographic) ordering, too.
Alike the 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)Groebner bases computed by this ordering give the most convenient
Groebner bases for solving the polynomial equations.
The only and serious shortcoming is the enormously long computation
time.
It is often observed that the number coefficients of the result becomes
very very long integers, especially if the ideal is 0-dimensional.
For such a case, it is empirically true for many cases
that i.e., computation by
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 corresponding 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 matrix.
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.
| [ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] |
This document was generated on December 22, 2024 using texi2html 5.0.