Type of Document	Dissertation
Author	Keller, Benjamin J.
URN	etd-405814212975790
Title	Algorithms and Orders for Finding Noncummutative Grobner Bases
Degree	PhD
Department	Computer Science
Advisory Committee	Advisor Name Title Allison, Donald C. S. Farkas, Daniel R. Keenan, Michael A. Shaffer, Clifford A. Green, Edward L. Committee Co-Chair Heath, Lenwood S. Committee Co-Chair
Keywords	none
Date of Defense	1997-03-17
Availability	unrestricted
Abstract The problem of choosing efficient algorithms and good admissible orders for computing Gröbner bases in noncommutative algebras is considered. Gröbner bases are an important tool that make many problems in polynomial algebra computationally tractable. However, the computation of Gröbner bases is expensive, and in noncommutative algebras is not guaranteed to terminate. The algorithm, together with the order used to determine the leading term of each polynomial, are known to affect the cost of the computation, and are the focus of this thesis. A Gröbner basis is a set of polynomials computed, using Buchberger's algorithm, from another set of polynomials. The noncommutative form of Buchberger's algorithm repeatedly constructs a new polynomial from a triple, which is a pair of polynomials whose leading terms overlap and form a nontrivial common multiple. The algorithm leaves a number of details underspecified, and can be altered to improve its behavior. A significant improvement is the development of a dynamic dictionary matching approach that efficiently solves the pattern matching problems of noncommutative Gröbner basis computations. Three algorithmic alternatives are considered: the strategy for selecting triples (selection), the strategy for removing triples from consideration (triple elimination), and the approach to keeping the set interreduced (set reduction). Experiments show that the selection strategy is generally more significant than the other techniques, with the best strategy being the one that chooses the triple with the shortest common multiple. The best triple elimination strategy ignoring resource constraints is the Gebauer-Müller strategy. However, another strategy is defined that can perform as well as the Gebauer-Müller strategy in less space. The experiments also show that the admissible order used to determine the leading term of a polynomial is more significant than the algorithm. Experiments indicate that the choice of order is dependent on the input set of polynomials, but also suggest that the length lexicographic order is a good choice for many problems. A more practical approach to chosing an order may be to develop heuristics that attempt to find an order that minimizes the number of overlaps considered during the computation.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    bjkdiss.pdf 1.88 Mb 00:08:41 00:04:28 00:03:54 00:01:57 00:00:10   etd.pdf 1.88 Mb 00:08:41 00:04:28 00:03:54 00:01:57 00:00:10

If you have questions or technical problems, please Contact DLA.