A Grobner Walk Implementation in Maple
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.