A case study of a multithreaded Buchberger normal form algorithm

Grobner 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 Grobner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Grobner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Grobner 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 Grobner 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.