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 AbstractThe 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.pdf1.88 Mb 00:08:41 00:04:28 00:03:54 00:01:57 00:00:10 etd.pdf1.88 Mb 00:08:41 00:04:28 00:03:54 00:01:57 00:00:10

Browse All Available ETDs by
( Author |
Department )

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