The F5 criterion revised
From MaRDI portal
Abstract: The purpose of this work is to generalize part of the theory behind Faugere's "F5" algorithm. This is one of the fastest known algorithms to compute a Groebner basis of a polynomial ideal I generated by polynomials f_{1},...,f_{m}. A major reason for this is what Faugere called the algorithm's "new" criterion, and we call "the F5 criterion"; it provides a sufficient condition for a set of polynomials G to be a Groebner basis. However, the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination. This paper introduces some new concepts that place the criterion in a more general setting: S-Groebner bases and primitive S-irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f_{1},...,f_{m} be a regular sequence.
Recommendations
Cites work
- scientific article; zbMATH DE number 3649988 (Why is no real title available?)
- scientific article; zbMATH DE number 3857249 (Why is no real title available?)
- scientific article; zbMATH DE number 1263375 (Why is no real title available?)
- scientific article; zbMATH DE number 2151220 (Why is no real title available?)
- scientific article; zbMATH DE number 2166957 (Why is no real title available?)
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
- On an installation of Buchberger's algorithm
Cited in
(33)- Signature-based algorithm under non-compatible term orders and its application to change of ordering
- Axioms for a theory of signature bases
- The termination of the F5 algorithm revisited
- Speeding up the GVW algorithm via a substituting method
- Extended \(F_5\) criteria
- scientific article; zbMATH DE number 1303429 (Why is no real title available?)
- A non-commutative \(F_5\) algorithm with an application to the computation of Loewy layers.
- The F5 algorithm in Buchberger's style
- A generalized criterion for signature related Gröbner basis algorithms
- A new algorithm for computing staggered linear bases
- Applying IsRewritten criterion on Buchberger algorithm
- The \(F5\) criterion revised
- Signature-based standard basis algorithm under the framework of GVW algorithm
- An improvement over the GVW algorithm for inhomogeneous polynomial systems
- A new proof for the correctness of the F5 algorithm
- scientific article; zbMATH DE number 2151220 (Why is no real title available?)
- On affine tropical F5 algorithms
- A survey on signature-based algorithms for computing Gröbner bases
- Generalization of the F5 algorithm for calculating Gröbner bases for polynomial ideals
- Simple signature based iterative algorithm for calculation of Gröbner bases
- On the computation of Gröbner bases for matrix-weighted homogeneous systems
- An analysis of inhomogeneous signature-based Gröbner basis computations
- On the construction of staggered linear bases
- Involutive bases algorithm incorporating F\(_5\) criterion
- A new framework for computing Gröbner bases
- Signature Gröbner bases, bases of syzygies and cofactor reconstruction in the free algebra
- Signature Gröbner bases in free algebras over rings
- Proof of the Faugère criterion for the F5 algorithm
- A signature-based algorithm for computing Gröbner bases over principal ideal domains
- Corrigendum to: ``The F5 criterion revised
- On the use of Buchberger criteria in \(\mathrm G^2\mathrm V\) algorithm for calculating Gröbner bases
- Predicting zero reductions in Gröbner basis computations
- scientific article; zbMATH DE number 5831023 (Why is no real title available?)
This page was built for publication: The F5 criterion revised
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275900)
