On the multi-threaded computation of integral polynomial greatest common divisors
Wolfgang Küchlin · 1991
We present a parallelization of the Brown-Collins algorithm in the PARSAC-2 Computer Algebra system, and we describe the design of our S- threads parallelization environment. PARSAC-2 is a parallel extension of SAC-2 built upon multiple threads of control provided by S-threads. The Brown-Collins algorithm computes the g.c.d. and its co-factors of two polynomials in Zp[x1,..., xr], r ≥ 2, by first reducing the problem to multiple g.c.d. calculations of modular homomorphic images (MHI) in Zp[x2,..., x r ], and then recovering the result by interpolation. After studying timings of the SAC-2 implementation, we first parallelize the interpolation algorithm, and then we parallelize the main MHI loop by executing the modular g.c.d. computations concurrently. We determine speed-up's and speed-up efficiencies over a wide range of polynomials.