Maria Francis, Thibaut Verron,
"A Signature-based Algorithm for Computing Gröbner Bases over Principal Ideal Domains"
, in Mathematics in Computer Science, Serie Online First, 2019, ISSN: 1661-8270
A Signature-based Algorithm for Computing Gröbner Bases over Principal Ideal Domains
Sprache des Titels:
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 (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).