A Gröbner Walk Implementation in Maple

Jeff Farr and Roman Pearce, Simon Fraser University

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

While the main ideas of the Gröbner 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 possible that a special selection strategy for Buchberger's algorithm may further streamline the walk. As a result, the Gröbner Walk has been included in only a few computer algebra packages.

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