GroebnerWalk -- Compute Groebner bases via the Groebner walk

The Groebner walk is a Groebner basis conversion algorithm. This means it takes a Groebner basis of an ideal with respect to one monomial order and changes it into a Groebner basis of the same ideal over a different monomial order. Conversion algorithms can be useful since sometimes when a Groebner basis over a difficult monomial order (such as lexicographic or an elimination order) is desired, it can be faster to compute a Groebner basis directly over an easier order (such as graded reverse lexicographic) and then convert rather than computing directly in the original order. Other examples of conversion algorithms include FGLM and Hilbert-driven Buchberger.

The Groebner walk performs conversion by traveling through the Groebner fan. The Groebner basis is the same for all vectors inside a cone of the fan, and when crossing a face into a new cone a (hopefully small) adjustment of the Groebner basis is all that must be computed. Further background and details can be found in the following resources:

Cox, Little, O'Shea - Using Algebraic Geometry (2005)

Amrhein, Gloor, Kuchlin - On the Walk (1997)

Collart, Kalkbrenner, Mall - Converting Bases with the Groebner Walk (1997)

Fukuda, Jensen, Lauritzen, Thomas - The Generic Grobner Walk (2007)

Tran - A Fast Algorithm for Grobner Basis Conversion and its Applications (2000)

In Macaulay2, monomial orders must be given as options to rings. For example, the following ideal has monomial order given by first using a weight vector and then breaking ties with graded reverse lexicographic.

i1 : R1 = QQ[x,y,z,u,v, MonomialOrder=>Weights=>{1,1,1,0,0}];

i2 : I1 = ideal(u + u^2 - 2*v - 2*u^2*v + 2*u*v^2 - x,
                -6*u + 2*v + v^2 - 5*v^3 + 2*u*v^2 - 4*u^2*v^2 - y,
                -2 + 2*u^2 + 6*v - 3*u^2*v^2 - z);

o2 : Ideal of R1

If we want a Groebner basis of I with respect to the monomial order given by using a different weight vector and then graded reverse lexicographic we could substitute and compute directly,

i3 : R2 = QQ[x,y,z,u,v, MonomialOrder=>Weights=>{0,0,0,1,1}];

i4 : I2 = sub(I1, R2);

o4 : Ideal of R2

i5 : elapsedTime gb I2
 -- 2.9699 seconds elapsed

o5 = GroebnerBasis[status: done; S-pairs encountered up to degree 16]

o5 : GroebnerBasis

but it is faster to compute directly in the first order and then use the Groebner walk.

i6 : elapsedTime groebnerWalk(gb I1, R2)
 -- 1.55581 seconds elapsed

o6 = GroebnerBasis[status: done; S-pairs encountered up to degree 0]

o6 : GroebnerBasis

The target ring must be the same ring as the ring of the starting ideal, except with different monomial order. The ring must be a polynomial ring over a field.

Author

• Dylan Peifer <[email protected]>

Version

This documentation describes version 1.0.0 of GroebnerWalk.

Source code

The source code from which this documentation is derived is in the file GroebnerWalk.m2.

Exports