A signature-based algorithm for computing Gröbner bases over principal ideal domains
From MaRDI portal
Publication:782709
DOI10.1007/S11786-019-00432-5zbMATH Open1454.13047arXiv1802.01388OpenAlexW2995980777MaRDI QIDQ782709FDOQ782709
Authors: Maria Francis, Thibaut Verron 
Publication date: 28 July 2020
Published in: Mathematics in Computer Science (Search for Journal in Brave)
Abstract: Signature-based algorithms have become a standard approach for Gr"obner 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"obner bases over commutative integral domains. It is adapted from a general version of M"oller'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).
Full work available at URL: https://arxiv.org/abs/1802.01388
Recommendations
- Signature-based algorithms to compute Gröbner bases
- A new signature-based algorithms for computing Gröbner bases
- A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras
- A survey on signature-based algorithms for computing Gröbner bases
- Signature-based algorithms for Gröbner bases over tate algebras
- A generalized criterion for signature related Gröbner basis algorithms
- A signature-based algorithm for computing Gröbner-Shirshov bases in skew solvable polynomial rings.
- On signature-based Gröbner bases over Euclidean rings
- Simple signature based iterative algorithm for calculation of Gröbner bases
- An efficient reduction strategy for signature-based algorithms to compute Gröbner basis
Cites Work
- The Magma algebra system. I: The user language
- A survey on signature-based algorithms for computing Gröbner bases
- The F5 criterion revised
- An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
- A new incremental algorithm for computing Groebner bases
- Title not available (Why is that?)
- Title not available (Why is that?)
- Practical Gröbner basis computation
- Signature-based algorithms to compute Gröbner bases
- F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases
- Title not available (Why is that?)
- A new framework for computing Gröbner bases
- Computing a Gröbner basis of a polynomial ideal over a Euclidean domain
- Effective computation of strong Gröbner bases over Euclidean domains
- On the construction of Gröbner bases using syzygies
- Applications of strong Gröbner bases over Euclidean domains
- On an installation of Buchberger's algorithm
- Signature rewriting in Gröbner basis computation
- On the complexity of the \(F_5\) Gröbner basis algorithm
- Reduced Gröbner bases in polynomial rings over a polynomial ring
- On ideal lattices, Gröbner bases and generalized hash functions
- On signature-based Gröbner bases over Euclidean rings
Cited In (9)
- Signature Gröbner bases in free algebras over rings
- Axioms for a theory of signature bases
- Efficient Gröbner bases computation over principal ideal rings
- Simple signature based iterative algorithm for calculation of Gröbner bases
- Title not available (Why is that?)
- Computing syzygies by Faugère's \(\mathbb{F}_{5}\) algorithm
- A new proof for the correctness of the F5 algorithm
- GVW algorithm over principal ideal domains
- On signature-based Gröbner bases over Euclidean rings
Uses Software
This page was built for publication: A signature-based algorithm for computing Gröbner bases over principal ideal domains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782709)
