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.

[img] Text
On Two Signature.pdf

Download (1MB)


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:
IITH CreatorsORCiD
Francis, Mariahttps://orcid.org/0000-0002-2537-5840
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: algorithms, polynomials over rings, principal ideal domains, signature-based algorithms
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 26 Apr 2022 10:28
Last Modified: 26 Apr 2022 10:28
URI: http://raiith.iith.ac.in/id/eprint/9257
Publisher URL: https://dl.acm.org/doi/10.1145/3452143.3465522
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9257 Statistics for this ePrint Item