A Dynamic F4 Algorithm To Compute Gröbner Bases

Document Type

Article

Publication Date

11-1-2020

Department

Mathematics

School

Mathematics and Natural Sciences

Abstract

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.

Publication Title

Applicable Algebra in Engineering, Communications and Computing

Volume

31

Issue

5-6

First Page

411

Last Page

434

Link to Full Text

Find in your library

Share

COinS