An analysis of inhomogeneous signature-based Gröbner basis computations (Q2437323)

The article considers some questions related to signature-based algorithms to compute Gröbner bases. Signature-based algorithms compute for each polynomial a ``signature'', which aims to be the leading term of its representation in a certain module. While this relationship does not always hold, that very fact allows the algorithm to avoid useless computations, as polynomials with the wrong signature always reduce to zero. On the other hand, the structure of a correct signature allows the algorithm to perform useful computations much more efficiently. The initial breakthrough on signature-based algorithms came with \textit{J.-C. Faugère}'s 2002 article, ``A new efficient algorithm for computing Gröbner bases without reduction to zero \(F_5\)'', [in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002, Lille, France, July 07--10, 2002. New York, NY: ACM Press. 75--83 (2002; Zbl 1072.68664)] which garnered a great deal of attention, but not much followup from other researchers for the next several years. So, while this article comes more than a decade after the original, it still addresses several fundamental questions related to such algorithms, offering important new insights. Besides this, it briefly summarizes several other algorithms and includes some comparisons related to the larger, theoretical questions. In particular, specialists in Gröbner basis computation are well aware that it is in some sense easier to compute the basis of a homogeneous polynomial system than of an inhomogeneous one. Alas, homogenizing an inhomogeneous system introduces solutions at the point of infinity, bringing penalties which offset or even cancel the benefits of a homogeneous computation. Faugère's report on \(F_5\) so strongly emphasized homogeneous systems that many researchers concluded the algorithm was inapt for the inhomogeneous case, and Eder spends some time pointing out that this is not the case. In particular, Theorem 4.2 of this work draws an explicit parallel between what he calls ``signature degree'' and the well-known ``sugar degree'', a well-known technique of bringing to inhomogeneous systems the ``smoothness'' of computing a Gröbner basis for a homogenized system, without incurring the penalties associated with homogenization. On the other hand, signatures do not completely ``sweeten'' the pot, as Section~5 explains (with the lovely title, ``Still, there is a sour taste left''). Unlike a sugar-based algorithm, signature-based algorithms must forbid some reductions in order to preserve the correct signature; otherwise, signature corruption would result, which in many cases leads to premature termination. This phenomenon, which Eder calls ``higher signature detection'', generates instead a new \(S\)-polynomial. Section 5 includes experiments that compare the ratios of these higher-signature detections to absolute reduction steps for some commonly used benchmarks, including a comparison using different module orderings to determine the signature. An important observation is that an incremental ordering such as POT typically generates a much, much larger ratio of higher signature detections than a non-incremental orderings such as Schreyer. This agrees with evidence found by other researchers that such non-incremental orderings can lend additional improvements to those inherent to signature-based algorithms.