On Two Signature Variants of Buchberger's Algorithm over Principal Ideal Domains

Francis, M. and Verron, T. (2021) On Two Signature Variants of Buchberger's Algorithm over Principal Ideal Domains. In: 46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021, 18 July 2021 through 23 July 2021, Virtual, Online.

Text
On Two Signature.pdf
Download (1MB)

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.

[error in script]

IITH Creators: