Date of Award
5-2011
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Chair/Advisor
Gao, Shuhong
Committee Member
Dean , Brian C
Committee Member
Dimitrova , Elena S
Committee Member
Kiessler , Peter C
Committee Member
Macauley , Matthew
Abstract
In this thesis, we present new algorithms for computing Groebner bases. The first algorithm, G2V, is incremental in the same fashion as F5 and F5C. At a typical step, one is given a Groebner basis G for an ideal I and any polynomial g, and it is desired to compute a Groebner basis for the new ideal , obtained from I by joining g. Let (I : g) denote the colon ideal of I divided by g. Our algorithm computes Groebner bases for I, g and (I : g) simultaneously. In previous algorithms, S-polynomials that reduce to zero are useless, in fact, F5 tries to avoid such reductions as much as possible. In our algorithm, however, these 'useless' S-polynomials give elements in (I : g) and are useful in speeding up the subsequent computations. Computer experiments on some benchmark examples indicate that our algorithm is much more efficient (two to ten times faster) than F5 and F5C.
Next, we present a more general algorithm that matches Buchberger's algorithm in simplicity and yet is more flexible than G2V. Given a list of polynomials, the new algorithm computes simultaneously a Groebner basis for the ideal generated by the polynomials and a Groebner basis for the leading terms of the syzygy module of the polynomials. For any term order for the ideal, one may vary the term order for the syzygy module. Under one term order for the syzygy module, the new algorithm specializes to the G2V algorithm, and under another term order for the syzygy module, the new algorithm may be several times faster than G2V, as indicated by computer experiments on benchmark examples.
Finally, we present a solid theoretical framework for G2V and GVW which makes the algorithm much more understandable. This theory also gives a major improvement of the GVW algorithm. A proof of termination is provided for all algorithms, and an argument is made that GVW computes the fewest number of generators for the signature based algorithms used by GVW and F5 (similarly for G2V and F5C).
Recommended Citation
Volny, Frank, "New Algorithms for Computing Groebner Bases" (2011). All Dissertations. 725.
https://tigerprints.clemson.edu/all_dissertations/725