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.
|
|
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,
|
|
|
but it is faster to compute directly in the first order and then use the Groebner walk.
|
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.
This documentation describes version 1.0.0 of GroebnerWalk.
If you have used this package in your research, please cite it as follows:
|
The object GroebnerWalk is a package, defined in GroebnerWalk.m2.
The source of this document is in GroebnerWalk.m2:435:0.