The general question addressed by this project is: Which performance increases are achievable in practice from parallelizing an existing large Computer Algebra application when using "threads" (lightweight processes) on a shared memory machine? In particular, what is the lowest level of algebraic computation at which significant speed-ups can be obtained by exploiting the medium-grained parallelism provided by threads? The concrete research objective is to develop a framework for parallel programming in the ALDES/SAC-2 Computer Algebra System, and to effectively parallelize a significant part of the existing system. The environment for parallelization will be C-threads on an Encore Multimax. System oriented work will modify SAC-2 to allow large scale development of a parallelized system, including running existing code in parallel. In algorithms oriented work, targets for parallelization include the existing algorithms for the computation of Cylindrical Algebraic Decomposition, polynomial resultants, polynomial GCD's, polynomial real-root isolation, and arithmetic in basic algebraic domains. The complete system will then provide empirical data which will help estimate the practical potential of new parallel algorithms proposed in the literature.
