F5C: a variant of Faugere's F5 algorithm with reduced Groebner bases
arXiv:0906.2967 · doi:10.1016/j.jsc.2010.06.019
Abstract
Faugere's F5 algorithm computes a Groebner basis incrementally, by computing a sequence of (non-reduced) Groebner bases. The authors describe a variant of F5, called F5C, that replaces each intermediate Groebner basis with its reduced Groebner basis. As a result, F5C considers fewer polynomials and performs substantially fewer polynomial reductions, so that it terminates more quickly. We also provide a generalization of Faugere's characterization theorem for Groebner bases.
31 pages, 4 tables; updated proof of characterization theorem
Cited by in corpus (21)
- A new conception for computing gröbner basis and its applications
- Resolvability of Hamming Graphs
- A survey on signature-based Gröbner basis computations
- A New Proof for the Correctness of F5 (F5-Like) Algorithm
- Syzygies Probing Scattering Amplitudes
- Signature-based algorithms for Gr{ö}bner bases over Tate algebras
- A Generic and Executable Formalization of Signature-Based Gröbner Basis Algorithms
- Modifying Faugère's F5 Algorithm to ensure termination
- Metric Dimension of Hamming Graphs and Applications to Computational Biology
- The F5 Algorithm in Buchberger's Style
- An analysis of inhomogeneous signature-based Gröbner basis computations
- A Generalized Criterion for Signature-based Algorithms to Compute Gröbner Bases
- Middle-Solving F4 to Compute Grobner bases for Cryptanalysis over GF(2)
- Middle-Solving Grobner bases algorithm for cryptanalysis over finite fields
- Algorithm for Solving Massively Underdefined Systems of Multivariate Quadratic Equations over Finite Fields
- An efficient reduction strategy for signature-based algorithms to compute Groebner basis
- A Signature-based Algorithm for computing Computing Gröbner Bases over Principal Ideal Domains
- A Monomial-Oriented GVW for Computing Gröbner Bases
- Signature-based algorithms to compute Groebner bases
- Improving incremental signature-based Groebner basis algorithms
- A Signature-based Algorithm for Computing the Nondegenerate Locus of a Polynomial System