Signature-based algorithms to compute Groebner bases

Abstract

This paper describes a Buchberger-style algorithm to compute a Groebner basis of a polynomial ideal, allowing for a selection strategy based on "signatures". We explain how three recent algorithms can be viewed as different strategies for the new algorithm, and how other selection strategies can be formulated. We describe a fourth as an example. We analyze the strategies both theoretically and empirically, leading to some surprising results.

appears in Proceedings of ISSAC 2011; includes minor revisions (a number of typos which make Section 2.2 difficult to follow)