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

Abstract: In this paper we give an insight into the behaviour of signature-based Gr"obner basis algorithms, like F5, G2V or SB, for inhomogeneous input. On the one hand, it seems that the restriction to sig-safe reductions puts a penalty on the performance. The lost connection between polynomial degree and signature degree can disallow lots of reductions and can lead to an overhead in the computations. On the other hand, the way critical pairs are sorted and corresponding s-polynomials are handled in signature-based algorithms is a very efficient one, strongly connected to sorting w.r.t. the well-known sugar degree of polynomials.

Review text

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.

Recommendations

Cites work

Cited in

(7)

Describes a project that uses

Uses Software

This page was built for publication: An analysis of inhomogeneous signature-based Gröbner basis computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437323)