Signature-based Möller's Algorithm for strong Gröbner bases over PIDs
Sprache des Titels:
Signature-based algorithms are the latest and most efficient approach as of today to compute Gröbner bases for polynomial systems over fields. Recently, possible extensions of these techniques
to general rings have attracted the attention of several authors.
In this paper, we present a signature-based version of Möller?s
classical variant of Buchberger?s algorithm for computing strong
Gröbner bases over Principal Ideal Domains (or PIDs). It ensures
that the signatures do not decrease during the algorithm, which
makes it possible to apply classical signature criteria for further
optimization. In particular, with the F5 criterion, the signature
version of Möller?s algorithm computes a Gröbner basis without
reductions to zero for a polynomial system given by a regular
sequence. We also show how Buchberger?s chain criterion can be
implemented so as to be compatible with the signatures.
We prove correctness and termination of the algorithm. Furthermore, we have written a toy implementation in Magma, allowing
us to quantitatively compare the efficiency of the various criteria
for eliminating S-pairs.