# Can we make Buchberger's algorithm faster for a given ideal if we are allowed to vary the monomial order?

Suppose we have a finite set of generators for an ideal $I \subset R := \Bbbk[x_1,\dotsc, x_n]$, where $\Bbbk$ is a field. If we choose a monomial ordering, then Buchberger's algorithm allows us to produce a Groebner basis for $I$. However, the size of the resulting Groebner basis can be enormous, and moreover can vary greatly depending on the monomial order chosen.

Sometimes, we have a reason for desiring a monomial order independent of $I$. (E.g., for elimination, we need an order with certain characteristics of lex; if we want to see of two sets of generators give the same ideal, we obviously want to use the same monomial order for both of them.) However, there are times when we may want to find a Groebner basis for $I$ with respect to some monomial, and we don't really care which. This could be useful, for instance, if we want to find a monomial $\Bbbk$-basis for $R/I$, and thereby (assuming $I$ is homogeneous) calculate the Hilbert polynomial of $I$.

Are there studies of algorithms and/or heuristics that design a monomial order based on the given generators of $I$ in an effort to produce a smaller Groebner basis for this particular ideal?

Ideally, it might be possible to choose a monomial order that has a good chance of outperforming grevlex on this particular generating set. At the very least, there should be some sort of heuristics for which grevlex order to choose (i.e., how the variables should be ordered).

-

You might investigate Singular, a software package for algebraic polynomial computations. I know little about it, but it does implement a so-called Hilbert-driven Buchberger algorithm, which (somehow!) finds "an appropriately chosen fast" ordering of the monomials, specifically to circumvent the problem that "the performance of Buchberger's algorithm is sensitive to the choice of monomial order." Their documentation provides one example with a $100 {\times}$ speedup.

This article by Manuel Kauers in Scholarpedia may help. Here are some quotes:

Change of Ordering

Some applications require Gröbner bases with respect to a particular ordering of the power products for which Buchberger's algorithm is not as efficient as for other orderings. In such situations it may be advantageous to first compute a Gröbner basis with respect to some ordering where Buchberger's algorithm runs faster and in a second step transform this Gröbner basis to a Gröbner basis for the desired ordering.

Gröbner Walk

Two different techniques for performing such a change of ordering are known. One is known as Gröbner walk. It is based on an interpretation of orderings as regions in a space. If two orderings correspond to regions which overlap, then a Gröbner basis for one of the orderings can be turned into a Gröbner basis for the other by calling Buchberger's algorithm on a small auxiliary problem for which it usually terminates quickly. When the regions for two orderings do not overlap, it is always possible to connect them by a path consisting of orderings where the regions of any two consecutive ones have an overlap. The transformation can then be done step by step, switching in each step to the next ordering on the path. [...]

Linear Algebra

The second technique uses linear algebra. If $G$ is a Gröbner basis for some ordering, then we have [...] Using this technique, [...], one can determine the elements of a Gröbner basis with respect to an ordering different from the ordering of $G$.

See the article for more details and references.

-
This looks interesting, but the way it is presented suggests that the approach is in some sense inverse to mine. The algorithm is presented as a way to circumvent the problem that "the performance of Buchberger's algorithm is sensitive to the choice of monomial order," so in particular, it may not be possible always to use grevlex. I want to take advantage of this sensitivity to choose a "good" monomial order for a given ideal, maybe even a monomial order that outperforms grevlex for this particular ideal. At least, there should be heuristics for ordering the variables. –  Charles Staats Jul 18 '11 at 19:12
Sorry if that was a wild goose chase, Charles! Perhaps the Gröbner Walk (now added above) is closer to what you want? –  Joseph O'Rourke Jul 18 '11 at 23:01
This is very interesting, and certainly more detailed (and with better references) than the Singular documentation. However, it still has the same basic issue: as far as I can tell (albeit without closely investigating the references), the question addressed is how to use a Groebner basis with respect to an efficient ordering to obtain a Groebner basis with respect to a less efficient ordering. My interest here is in how to find an efficient ordering in the first place. –  Charles Staats Jul 18 '11 at 23:27