High Performance Symbolic Computing and Challenges of Computer Algebra

**Data-flow multithreaded parallelism in computer algebra algorithms**

- The Cantor-Zassenhaus algorithm for the factorization of polynomials over finite fields
- The Gaussian Elimination algorithm for rank calculations of sparse matrices with entries from a finite field

This talk introduces the mechanism of on-the-fly data-flow analysis in order to exploit the inherent parallelism in most algebraic algorithms. We present results necessary to guarantee efficient parallel execution with respect to time and space on various distributed architectures, SMP or networks of workstations. We propose a programming model based on a depth-first evaluation ordering.

The talk is illustrated with two classical computer algebra algorithms, both having a high degree of parallelism and take advantage of ordering mechanism that may depend on the target architecture:

Jean-Louis Roch

ENSIMAG-INPG

Jean-Louis.Roch@imag.fr

Joint work with: Thierry Gautier, Jean-Guillaume Dumas and Gilles Villard

IMACS ACA'98 Electronic Proceedings