Sweetening the sour taste of inhomogeneous signature-based Groebner basis computations
Christian Eder · arXiv (Cornell University) · 2012
In this paper we want to give an insight in the rather unknown behaviour of signature-based Groebner basis algorithms, like F5, G2V, or GVW, for inhomogeneous input. On the one hand, it seems that the restriction to sig-safe reductions in those algorithms puts a huge penalty on their performance. The lost connection between polynomial degree and signature degree can disallow lots of reductions and lead to a huge overhead in the computations. On the other hand, the way critical pairs are sorted and the corresponding s-polynomials are handled is a quite good one. We show in detail the strong connection to the sorting of critical pairs w.r.t. well-known sugar degree of polynomials. Those properties hold for signature-based Groebner basis algorithms in general, not depending on specific implementations of the underlying criteria to discard useless critical pairs.