Persistent Link:
http://hdl.handle.net/10150/305141
Title:
A Case Study of A Multithreaded Buchberger Normal Form Algorithm
Author:
Linfoot, Andy James
Issue Date:
2006
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Embargo:
Dissertation Not Available (per Author's Request); UA Affiliates can find item in ProQuest Dissertations database
Abstract:
Groebner bases have many applications in mathematics, science, and engineering. This dissertation deals with the algorithmic aspects of computing these bases. The dissertation begins with a brief introduction of fundamental concepts about Groebner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Groebner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Groebner basis primarily stems from the calculation of normal forms. This is established by studying run profiles of various computations. This leads to two options of making Groebner basis techniques more practical. They are to reduce the complexity by developing new algorithms (heuristics) or reduce running time of normal form calculations by introducing concurrency. The later approach is taken in the remainder of the dissertation where a multithreaded normal form algorithm is presented and discussed. It is shown with a simple example that the new algorithm demonstrates a speedup and scalability. The algorithm also has the advantage of being completion strategy independent. We conclude with an outline of future research involving the new algorithm.
Type:
text; Electronic Dissertation
Keywords:
Applied Mathematics; Symbolic Computation; Groebner Bases; Parallel Computing; Computer Algebra
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College
Degree Grantor:
University of Arizona

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleA Case Study of A Multithreaded Buchberger Normal Form Algorithmen_US
dc.creatorLinfoot, Andy Jamesen_US
dc.contributor.authorLinfoot, Andy Jamesen_US
dc.date.issued2006-
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.releaseDissertation Not Available (per Author's Request); UA Affiliates can find item in ProQuest Dissertations databaseen_US
dc.description.abstractGroebner bases have many applications in mathematics, science, and engineering. This dissertation deals with the algorithmic aspects of computing these bases. The dissertation begins with a brief introduction of fundamental concepts about Groebner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Groebner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Groebner basis primarily stems from the calculation of normal forms. This is established by studying run profiles of various computations. This leads to two options of making Groebner basis techniques more practical. They are to reduce the complexity by developing new algorithms (heuristics) or reduce running time of normal form calculations by introducing concurrency. The later approach is taken in the remainder of the dissertation where a multithreaded normal form algorithm is presented and discussed. It is shown with a simple example that the new algorithm demonstrates a speedup and scalability. The algorithm also has the advantage of being completion strategy independent. We conclude with an outline of future research involving the new algorithm.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectApplied Mathematicsen_US
dc.subjectSymbolic Computationen_US
dc.subjectGroebner Basesen_US
dc.subjectParallel Computingen_US
dc.subjectComputer Algebraen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.