Show simple item record

dc.contributor.authorKeller, Benjamin J.en_US
dc.date.accessioned2014-03-14T20:21:54Z
dc.date.available2014-03-14T20:21:54Z
dc.date.issued1997-03-17en_US
dc.identifier.otheretd-405814212975790en_US
dc.identifier.urihttp://hdl.handle.net/10919/30506
dc.description.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.en_US
dc.publisherVirginia Techen_US
dc.relation.haspartetd.pdfen_US
dc.relation.haspartbjkdiss.pdfen_US
dc.rightsI hereby grant to Virginia Tech or its agents the right to archive and to make available my thesis or dissertation in whole or in part in the University Libraries in all forms of media, now or hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation.en_US
dc.subjectnoneen_US
dc.titleAlgorithms and Orders for Finding Noncummutative Grobner Basesen_US
dc.typeDissertationen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Scienceen_US
dc.contributor.committeememberFarkas, Daniel R.en_US
dc.contributor.committeememberAllison, Donald C. S.en_US
dc.contributor.committeememberShaffer, Clifford A.en_US
dc.contributor.committeememberKeenan, Michael A.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-405814212975790/en_US
dc.contributor.committeecochairGreen, Edward L.en_US
dc.contributor.committeecochairHeath, Lenwood S.en_US
dc.date.sdate1998-07-17en_US
dc.date.rdate1997-03-17
dc.date.adate1997-03-17en_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record