lex_hensel, lex_tl, tolex, tolex_d, tolex_tl

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].)
  1. Compute a Groebner basis G0 with respect to vlist1 and order. (Only in lex_hensel(). )
  2. 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.
  3. Compute NF, the set of all the normal forms with respect to G0 of terms appearing in Gp.
  4. 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.
  5. Solve Lf by Hensel lifting, starting from the unique mod p solution.
  6. 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].)
  1. Compute a Groebner basis G0 with respect to vlist1 and order. (Only in lex_tl(). )
  2. If G0 is not zero-dimensional, 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.
  3. If G0 is zero-dimensional, 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 zero-dimensional 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.