most recent 30 from http://mathoverflow.net 2013-05-20T03:24:34Z http://mathoverflow.net/feeds/question/70579 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70579/can-we-make-buchbergers-algorithm-faster-for-a-given-ideal-if-we-are-allowed-to Charles Staats 2011-07-17T23:43:53Z 2011-07-18T23:08:16Z

<p>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.</p> <p>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 <i>some</i> 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$.</p> <blockquote> <p>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?</p> </blockquote> <p>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).</p>

http://mathoverflow.net/questions/70579/can-we-make-buchbergers-algorithm-faster-for-a-given-ideal-if-we-are-allowed-to/70581#70581 Joseph O'Rourke 2011-07-17T23:57:36Z 2011-07-18T23:08:16Z

<p>You might investigate <a href="http://www.singular.uni-kl.de/" rel="nofollow">Singular</a>, a software package for algebraic polynomial computations. I know little about it, but it does implement a so-called <em><a href="http://www.singular.uni-kl.de/Manual/3-0-3/sing_544.htm" rel="nofollow">Hilbert-driven Buchberger algorithm</a></em>, 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.</p> <p><hr /> <a href="http://www.scholarpedia.org/article/Buchberger%27s_algorithm#Selection_Strategies" rel="nofollow">This article by Manuel Kauers in Scholarpedia</a> may help. Here are some quotes:</p> <blockquote> <p><b>Change of Ordering</b></p> <p>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.</p> <p><em>Gröbner Walk</em></p> <p>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. [...]</p> <p><em>Linear Algebra</em></p> <p>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$.</p> </blockquote> <p>See the article for more details and references.</p>