F4 algorithm
E838596
The F4 algorithm is an efficient method for computing Gröbner bases using structured linear algebra techniques to speed up polynomial ideal calculations.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
Gröbner basis algorithm
ⓘ
algorithm ⓘ |
| advantage |
better use of cache and memory hierarchy via dense linear algebra
ⓘ
efficient handling of large polynomial systems ⓘ significant speedup over classical Buchberger algorithm ⓘ |
| application |
algebraic cryptanalysis
ⓘ
computing algebraic varieties ⓘ computing elimination ideals ⓘ solving systems of polynomial equations ⓘ |
| author | Jean-Charles Faugère NERFINISHED ⓘ |
| basedOn | Buchberger algorithm NERFINISHED ⓘ |
| category | symbolic computation algorithm ⓘ |
| complexityDependsOn |
degrees of input polynomials
ⓘ
number of variables ⓘ sparsity of polynomials ⓘ term ordering ⓘ |
| computes | Gröbner basis of a polynomial ideal ⓘ |
| coreIdea |
batch S-polynomial computations into linear algebra problems
ⓘ
replace repeated polynomial reductions by simultaneous reductions via matrix operations ⓘ |
| field |
computational algebraic geometry
ⓘ
computational commutative algebra ⓘ computer algebra ⓘ |
| implementedIn |
Magma computer algebra system
NERFINISHED
ⓘ
Maple computer algebra system NERFINISHED ⓘ SageMath computer algebra system NERFINISHED ⓘ Singular computer algebra system ⓘ |
| improvesOn | Buchberger algorithm NERFINISHED ⓘ |
| influenced |
F5 algorithm
NERFINISHED
ⓘ
later Gröbner basis algorithms ⓘ |
| input | finite set of multivariate polynomials ⓘ |
| namedAfter | Jean-Charles Faugère NERFINISHED ⓘ |
| optimization |
selection strategies for critical pairs
ⓘ
sparse matrix techniques ⓘ symbolic preprocessing before matrix construction ⓘ |
| output | Gröbner basis NERFINISHED ⓘ |
| publishedIn | Journal of Pure and Applied Algebra NERFINISHED ⓘ |
| purpose | computing Gröbner bases ⓘ |
| relatedTo |
Buchberger algorithm
NERFINISHED
ⓘ
F5 algorithm NERFINISHED ⓘ Macaulay matrix method NERFINISHED ⓘ |
| requires |
field arithmetic
ⓘ
monomial ordering ⓘ |
| technique |
construction of Macaulay matrices
ⓘ
row-reduction of coefficient matrices ⓘ |
| titleOfOriginalPaper | A new efficient algorithm for computing Gröbner bases (F4) NERFINISHED ⓘ |
| uses |
Gaussian elimination
NERFINISHED
ⓘ
structured linear algebra ⓘ |
| worksOver | polynomial rings over fields ⓘ |
| yearProposed | 1999 ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.