COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Gröbner basis algorithms
by Dellaca, Roger D., M.S., California State University, Long Beach, 2009, 130; 1466198
Abstract (Summary)

This thesis considers the correctness and termination of two Gröbner basis algorithms. After developing the theory of Gröbner bases, reviewing standard efficiencies, and giving an example of their use, we examine a revised Staggered Linear Basis algorithm and the F5 algorithm.

The revised Staggered Linear Basis algorithm, given by Mora as an instructive example, includes a small modification of the original algorithm. We establish by counterexample that it does not always terminate, and give a rigorous proof of its correctness if it does terminate. We also show that the original Staggered Linear Basis algorithm is not correct.

Faugère's F5 algorithm appears to be faster than previous algorithms for computing Gröbner bases. As of this writing, a few demonstration implementations exist, but efficient, compiled implementations are still not widely available. Its correctness has been proven, which we show, but its termination is an open question, which we discuss.

Finally, we make some observations on tests performed with the algorithms. In particular, we observe that two published versions of the CritPair subroutine of F5 compute the same number of polynomials, leading to a conjecture that certain pairs that are not normalized are also rewritable.

Indexing (document details)
Advisor: Brevik, John
School: California State University, Long Beach
School Location: United States -- California
Source: MAI 47/05M, Masters Abstracts International
Subjects: Mathematics
Publication Number: 1466198
ISBN: 978-1-109-16782-5
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy