With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
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.
Advisor: | Brevik, John |
Commitee: | |
School: | California State University, Long Beach |
School Location: | United States -- California |
Source: | MAI 47/05M, Masters Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Mathematics |
Keywords: | |
Publication Number: | 1466198 |
ISBN: | 978-1-109-16782-5 |