A Signature-Based Algorithm for Computing Gröbner Bases over Principal Ideal Domains

Francis, Maria and Verron, Thibaut (2020) A Signature-Based Algorithm for Computing Gröbner Bases over Principal Ideal Domains. Mathematics in Computer Science, 14 (2). pp. 1-16. ISSN 1661-8270 (In Press)

Text
Mathematics_in_Computer_Science.pdf - Published Version
Available under License Creative Commons Attribution.
Download (356kB)

Abstract

Signature-based algorithms have become a standard approach for Gröbner basis computations for polynomial systems over fields, but how to extend these techniques to coefficients in general rings is not yet as well understood. In this paper, we present a proof-of-concept signature-based algorithm for computing Gröbner bases over commutative integral domains. It is adapted from a general version of Möller’s algorithm (J Symb Comput 6(2–3), 345–359, 1988) which considers reductions by multiple polynomials at each step. This algorithm performs reductions with non-decreasing signatures, and in particular, signature drops do not occur. When the coefficients are from a principal ideal domain (e.g. the ring of integers or the ring of univariate polynomials over a field), we prove correctness and termination of the algorithm, and we show how to use signature properties to implement classic signature-based criteria to eliminate some redundant reductions. In particular, if the input is a regular sequence, the algorithm operates without any reduction to 0. We have written a toy implementation of the algorithm in Magma. Early experimental results suggest that the algorithm might even be correct and terminate in a more general setting, for polynomials over a unique factorization domain (e.g. the ring of multivariate polynomials over a field or a PID).

[error in script]

IITH Creators:

IITH Creators	ORCiD
Francis, Maria	https://orcid.org/0000-0002-2537-5840

Item Type:

Article

Additional Information:

Open access funding provided by Johannes Kepler University Linz. The authors thank C. Eder and anonymous referees for helpful suggestions, M. Ceria and T. Mora for a fruitful discussion on the syzygy paradigm for Gröbner basis algorithms, and M. Kauers for his valuable insights and comments all through the elaboration of this work.

Uncontrolled Keywords:

Algorithms, Gröbner bases, Polynomials over rings, Principal ideal domains, Signature-based algorithms, Indexed in Scopus

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

Team Library

Date Deposited:

14 Jan 2020 04:53

Last Modified:

22 Oct 2022 11:34