Sparse interpolation and a fast parallel polynomial GCD algorithm
Michael Monagan, CECM, Simon Fraser University
Wednesday July 13th, K9509, 12:30pm.
Abstract We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. One obstacle is unlucky evaluation points. In the talk we will explain the Ben-Or/Tiwari sparse interpolation and the characterization and treatment of unlucky evaluation points. We have implemented the algorithm in Cilk C for 31, 63 and 127 bit primes. We compare it with Maple and Magma's implementations of Zippel's sparse GCD algorithm on some large GCD problems. This is joint work with Jiaxiong Hu.