Parallel algorithms and implementations for the Grobner bases algorithm and the characteristic sets method

The need for high computational power has always driven research in computer algebra. The recent advances in technology have made parallel machines a reality within reach of a large portion of the scientific community. The parallel algorithms have, therefore, assumed increasing importance in numerical and symbolic computation techniques.; This dissertation presents new and improved parallel implementations for two important and advanced mathematical algorithms: the Grobner Bases algorithm and the Characteristic Sets method. PVM-based parallel/distributed computation tools have been designed, implemented, and applied to the two algorithms. The tools make PVM easier to use and applicable to a wider class of computations. The applications show how advanced algebraic algorithms can take advantage of modern parallel/distributed computing with the aid of such tools. The tools and interfaces described include PvmJobs (a general bag-of-jobs library that works with any user created job structure in a master/slave paradigm) and the SaclibPvm (a simple software package interfacing SACLIB to PVM). The ability to interface symbolic computation to PVM allows us to tackle the parallelization of the Grobner Bases algorithm and the Characteristic Sets method, two very compute intensive algorithms important in algebraic computations.; The sources of parallelism in the Grobner Bases algorithm and the Characteristic Sets method have been investigated. The parallel implementations of the two algorithms have been conducted on a network of workstations and on an actual parallel processor, the CRAY T3E. The performance of the implementations has been evaluated and the experiments have demonstrated significant gains by employing parallelism in these algorithms. Empirical observations suggest that large speedups can be obtained when reasonable parallelism is exploited. These algorithms, their parallelization, and experimental results are presented.