Axioms for a theory of signature bases

DOI10.1016/J.JSC.2023.102275arXiv2210.13788OpenAlexW4307416510MaRDI QIDQ6149142FDOQ6149142

Authors: Pierre Lairez 

Publication date: 5 February 2024

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Twenty years after the discovery of the F5 algorithm, Gr"obner bases with signatures are still challenging to understand and to adapt to different settings. This contrasts with Buchberger's algorithm, which we can bend in many directions keeping correctness and termination obvious. I propose an axiomatic approach to Gr"obner bases with signatures with the purpose of uncoupling the theory and the algorithms, and giving general results applicable in many different settings (e.g. Gr"obner for submodules, F4-style reduction, noncommutative rings, non-Noetherian settings, etc.).

Full work available at URL: https://arxiv.org/abs/2210.13788

Recommendations

• A survey on signature-based algorithms for computing Gröbner bases
• Signature-based algorithms to compute Gröbner bases
• A new signature-based algorithms for computing Gröbner bases
• Simple signature based iterative algorithm for calculation of Gröbner bases
• A generalized criterion for signature related Gröbner basis algorithms

zbMATH Keywords

F5 algorithmGröbner basissignature basis

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• The Magma algebra system. I: The user language
• Extending the GVW Algorithm to Local Ring
• Ideals, Varieties, and Algorithms
• Title not available (Why is that?)
• An introduction to commutative and noncommutative Gröbner bases
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• A survey on signature-based algorithms for computing Gröbner bases
• Polynomial algorithms in computer algebra
• 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?)
• Signature-based algorithms for Gröbner bases over tate algebras
• Practical Gröbner basis computation
• A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras
• Signature-based algorithms to compute Gröbner bases
• A signature-based algorithm for computing Gröbner bases over principal ideal domains
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Title not available (Why is that?)
• Title not available (Why is that?)
• Advances in Cryptology - CRYPTO 2003
• Title not available (Why is that?)
• A new framework for computing Gröbner bases
• Title not available (Why is that?)
• Termination of the F5 algorithm
• A new proof for the correctness of the F5 algorithm
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Extended \(F_5\) criteria
• On an installation of Buchberger's algorithm
• Ordering by Divisibility in Abstract Algebras
• Hilbert functions and the Buchberger algorithm
• Corrigendum to: ``The F5 criterion revised
• Signature rewriting in Gröbner basis computation
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Title not available (Why is that?)
• On signature-based Gröbner bases over Euclidean rings
• Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra
• Methods for computing in algebraic geometry and commutative algebra
• On the construction of staggered linear bases
• A tropical F5 algorithm
• On Affine Tropical F5 Algorithms
• Signature Gröbner bases in free algebras over rings
• Gröbner basis over semigroup algebras. Algorithms and applications for sparse polynomial systems
• A signature-based algorithm for computing the nondegenerate locus of a polynomial system

Cited In (1)

• Short proofs of ideal membership

This page was built for publication: Axioms for a theory of signature bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149142)