Combinatorial Criteria for Grobner Bases
No Thumbnail Available
Files
Date
2005-07-21
Authors
Journal Title
Series/Report No.
Journal ISSN
Volume Title
Publisher
Abstract
Both the computation and the detection of Gröbner bases require a criterion that decides whether a set of polynomials is a Gröbner basis. The most fundamental decision criterion is the reduction of all S-polynomials to zero. However, S-polynomial reduction is expensive in terms of time and storage, so a number of researchers have investigated the question of when we can avoid S-polynomial reduction. Certain results can be considered "combinatorial", because they are criteria on the leading terms, which are determined by integers. Our research builds on these results; this thesis presents combinatorial criteria for Gröbner bases.
The first part of this thesis reviews the relevant literature on Gröbner bases and skipping S-polynomial reduction. The second part considers criteria for skipping a fixed number of S-polynomial reductions. The first two theorems of part two show howto apply Buchberger's criteria to obtain necessary and sufficient conditions for skipping all S-polynomial reductions, and for skipping all but one S-polynomial reductions. The third theorem considers the question of skipping all but two Spolynomial reductions; we have found that this problem requires new criteria on leading terms. We provide one new criterion that solves this problem for a set of three polynomials; for larger sets, the problem remains open.
The final part of this thesis considers Gröbner basis detection. After a brief review of a previous result that requires S-polynomial reduction, we provide a new result which takes a completely different approach, avoiding S-polynomial reduction completely.
Throughout the latter two parts, we provide some statistical analysis and experimental results.
Description
Keywords
S-polynomial reduction, Gröbner basis detection, combinatorial criteria, Gröbner bases
Citation
Degree
PhD
Discipline
Mathematics