A parallel lisp and multivariate polynomial GCD implementation

Abstract

This thesis is concerned with the intersection of two fields of study - computer algebra and parallel processing. The operation of multivariate polynomial greatest common divisor (gcd), an important and fundamental computer algebra operation, is investigated for amenability to parallelisation following the investigation of a suitable environment for implementation of a parallel computer algebra algorithm. After researching the requirements of a parallel computer algebra system, these were matched as closely as possible to available hardware. The choice of an array of transputers as the hardware system lead to the development of a parallel lisp for such a system as there was none readily available. The result was a useful, experimental, coarse-grained, message-passing parallel lisp (Tlisp) based on the eval-server model where each processor in the array (configured in a tree) executes its own lisp process, reading, evaluating and printing s-expressions independently of the others, but with facilities for passing s-expressions to and from its neighbours. Following an appraisal of algorithms available for calculating multivariate polynomial gcds, Zippel’s sparse modular gcd algorithm was selected as the most suitable candidate for parallelisation and implementation in Tlisp. Evaluation of the performance of both Tlisp and the parallel gcd algorithm was achieved by detailed examination of how they performed during execution for a range of test data. The results of the performance experiments and the practical experience gained from a working parallel lisp system and its implementation of an important computer algebra algorithm clearly show that there is much potential for a medium- to coarse-grained message-passing parallel system in the quest for a suitable system for parallel computer algebra.