F_5 algorithm
Plan
- Because the original paper includes many errors and lacks strictness, read Steger’s thesis instead first.
- Then read F5C paper to improve it.
- Read the paper on termination and apply its argument to F5C.
Current progress
- Reading Steger’s thesis. (2014/04/29)
- Implementing F_5, but is not yet working correctly. (2014/05/25)
- It turns out that F_5 is for homogeneous ideals, so I’m planning to read Eder and implement similar algorithm for inhomogeneous ideals.
- To make situation clear, I’m reading the articles on general signature-based algorithms (such as Eder’s papers (1, 2) and G2V)
Papers
- Improving incremental signature-based Gröbner basis algorithms
- Paper on the improvements for signature-based algorithms. A New Incremental Algorithm for Computing Groebner Bases
- The signature-based algorithm for general ideals (called G2V algorithm). On the Criteria of the F5 Algorithm
- Paper on correctness of Rewritten criteria and involves implementation in SINGULAR. Faugère’s F5 Algorithm
- Pseudocode of F5 by co-implementor of SINGULAR implementation presented in Eder’s paper. An analysis of inhomogeneous signature-based Gröbner basis computations
- Paper on signature-based Gröbner basis computation algorithms. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)
- Original paper. This includes some errors and have an issue on the proof of termination. Faugère’s F5 Algorithm Revisited
- More accurate and comprehensive description on F_5 algorithm. This paper notes on termination, but doesn’t guarantee termination for general inputs. F5C: a variant of Faugère’s F5 algorithm with reduced Gröbner bases
- Improved version of F5 algorithm, which computes reduced bases in internal computation. This algorithm is not proven to be terminate for general input cases. Faugère’s F5 algorithm: variants and termination issues
- A short slide on F5 algorithm. This discusses on improvements and how to make F5 algorithm to terminate for general cases. Modifying Faugère’s F5 Algorithm to Ensure Termination
- This paper discusses several ways to make F5 algorithm terminate for not only regular sequences but also general cases.
F_4 algorithm
A naive implementation has been done before GSoC starts. As we have to implement more efficient matrix triangulation, I’ll read the following papers:
- A new efficient algorithm for computing Groebner basis F4
- Original paper. Current implementation is based on this paper. An Implementation of Faugèere’s F4 Algorithm for Computing Gröbner Bases
- Paper on the detail of the implementation of F4. Maybe informative for matrix triangulation methods.
structured Gaussian Elimination
Cabarcas’s paper suggests that it’d be better to use the simplified version of structured Gaussian Elimination but not describe the detail of its algorithm (for example, how to determine columns “light” or “heavy”).
Here is some references which might be useful: