Go to the first, previous, next, last section, table of contents.
 lex_hensel(plist,vlist1,order,vlist2,homo)

 lex_tl(plist,vlist1,order,vlist2,homo)

: Groebner basis computation with respect to a lex order by change of ordering
 tolex(plist,vlist1,order,vlist2)

 tolex_d(plist,vlist1,order,vlist2,procs)

 tolex_tl(plist,vlist1,order,vlist2,homo)

:: Groebner basis computation with respect to a lex order by change of ordering, starting from a Groebner basis
 return

list
 plist, vlist1, vlist2, procs

list
 order

number, list or matrix
 homo

flag

These functions are defined in `gr' in the standard library
directory.

lex_hensel()
and lex_tl()
first compute a Groebner basis
with respect to the variable order vlist1 and the order type order.
Then the Groebner basis is converted into a lex order Groebner basis
with respect to the varable order vlist2.

tolex()
and tolex_tl()
convert a Groebner basis plist
with respect to the variable order vlist1 and the order type order
into a lex order Groebner basis
with respect to the varable order vlist2.
tolex_d()
does computations of basis elements in tolex()
in parallel on the processes in a child process list procs.

In
lex_hensel()
and tolex_hensel()
a lex order Groebner basis
is computed as follows.(Refer to [Noro,Yokoyama]
.)

Compute a Groebner basis G0 with respect to vlist1 and order.
(Only in
lex_hensel()
. )

Choose a prime which does not divide head coefficients of elements in G0
with respect to vlist1 and order. Then compute a lex order
Groebner basis Gp over GF(p) with respect to vlist2.

Compute NF, the set of all the normal forms with respect to
G0 of terms appearing in Gp.

For each element f in Gp, replace coefficients and terms in f
with undetermined coefficients and the corresponding polynomials in NF
respectively, and generate a system of liear equation Lf by equating
the coefficients of terms in the replaced polynomial with 0.

Solve Lf by Hensel lifting, starting from the unique mod p
solution.

If all the linear equations generated from the elements in Gp
could be solved, then the set of solutions corresponds to a lex order
Groebner basis. Otherwise redo the whole process with another p.

In
lex_tl()
and tolex_tl()
a lex order Groebner basis
is computed as follows.(Refer to [Noro,Yokoyama]
.)

Compute a Groebner basis G0 with respect to vlist1 and order.
(Only in
lex_tl()
. )

If G0 is not zerodimensional, choose a prime which does not divide
head coefficients of elements in G0 with respect to vlist1 and
order. Then compute a candidate of a lex order Groebner basis
via trace lifting with p. If it succeeds the candidate is indeed
a lex order Groebner basis without any check. Otherwise redo the whole
process with another p.

If G0 is zerodimensional, starting from G0,
compute a Groebner basis G1 with respect to an elimination order
to eliminate variables other than the last varibale in vlist2.
Then compute a lex order Groebner basis stating from G1. These
computations are done by trace lifting and the selection of a mudulus
p is the same as in non zerodimensional cases.

Computations with rational function coefficients can be done only by
lex_tl()
and tolex_tl()
.

If
homo
is not equal to 0, homogenization is used in Buchberger
algorithm.

The CPU time shown after an execution of
tolex_d()
indicates
that of the master process, and it does not include the time in child
processes.
[78] K=katsura(5)$
30msec + gc : 20msec
[79] V=[u5,u4,u3,u2,u1,u0]$
0msec
[80] G0=hgr(K,V,2)$
91.558sec + gc : 15.583sec
[81] G1=lex_hensel(K,V,0,V,0)$
49.049sec + gc : 9.961sec
[82] G2=lex_tl(K,V,0,V,1)$
31.186sec + gc : 3.500sec
[83] gb_comp(G0,G1);
1
10msec
[84] gb_comp(G0,G2);
1
 References

section
dp_gr_main
, dp_gr_mod_main
,
section dp_ord
, section Distributed computation
Go to the first, previous, next, last section, table of contents.