Faugère F5 algorithm (Gröbner Bases Gröbner Bases)

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(C(n+D_{reg}, D_{reg})$^{\omega}) where omega is the exponent on matrix multiplication

Space Complexity

$O(C(n+D_{reg}, D_{reg})$^{2})? words

(Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$))

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2002

Reference

https://dl.acm.org/doi/10.1145/780506.780516