A Grobner Walk Implementation in Maple

Jeff Farr

June 2nd, 2004.

Nearly a decade ago, Collart, Kalkbrener and Mall introduced a new method
for Grobner basis conversion, the Grobner Walk. Like the well-known FGLM 
algorithm, the Grobner walk is used to change a Grobner basis of an ideal 
with a given order to a Grobner basis of the ideal with respect to a new 
order. Unlike FGLM, though, the Grobner Walk does not require the ideal 
to be zero-dimensional.

While the main ideas of the Grobner Walk are straightforward, the actual
implementation of the algorithm is less understood. For example, it is not
clear exactly what path should be used for "walking" in the general case;
also, it is poossible that a special selection strategy for Buchberger's
algorithm may further streamline the walk. As a result, the Grobner Walk 
has been included in only a few computer algebra packages.

Addressing these questions is important as many applications require a
Grobner basis under lex order, which is much too hard to compute directly.
Further, some computational data already has suggested that the Grobner
Walk could outperform FGLM. We present some of these issues as they have
been encountered in our preliminary implementation in Maple.