A Dynamic F4 Algorithm To Compute Gröbner Bases
Mathematics and Natural Sciences
The F4 algorithm re-imagines Buchberger’s algorithm as the row reduction of a Macaulay matrix: each row corresponds to a polynomial; each reduction of one row by another corresponds to one step of reducing an S-polynomial; and any row that completes reduction with a new pivot position corresponds to a new element of the basis. On the other hand, each column corresponds to a term, so that while it is common in linear algebra to exchange a matrix’s columns during row reduction, this has not been done in F4-style algorithms, as it runs the risk of producing an incorrect result. We show that it is possible to adapt an analogous, “dynamic” technique for Buchberger-style algorithms to F4-style algorithms, and we examine its behavior on some commonly referenced benchmark ideals.
Applicable Algebra in Engineering, Communications and Computing
(2020). A Dynamic F4 Algorithm To Compute Gröbner Bases. Applicable Algebra in Engineering, Communications and Computing, 31(5-6), 411-434.
Available at: https://aquila.usm.edu/fac_pubs/19082