Header menu link for other important links
X
On Two Signature Variants of Buchberger's Algorithm over Principal Ideal Domains
, T. Verron
Published in Association for Computing Machinery
2021
Pages: 139 - 146
Abstract
Signature-based algorithms have brought large improvements in the performances of Gröbner bases algorithms for polynomial systems over fields. Furthermore, they yield additional data which can be used, for example, to compute the module of syzygies of an ideal or to compute coefficients in terms of the input generators. In this paper, we examine two variants of Buchberger's algorithm to compute Gröbner bases over principal ideal domains, with the addition of signatures. The first one is adapted from Kandri-Rody and Kapur's algorithm [17], whereas the second one uses the ideas developed in the algorithms by L. Pan [25] and D. Lichtblau [18]. The differences in constructions between the algorithms entail differences in the operations which are compatible with the signatures, and in the criteria which can be used to discard elements. We prove that both algorithms are correct and discuss their relative performances in a prototype implementation in Magma. © 2021 ACM.