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.