A fast parallel sparse polynomial GCD algorithm. (July 2021) - Hu, Jiaxiong; Monagan, Michael
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. We have implemented our algorithm in C for primes of various sizes and have parallelized it using Cilk C. We compare our implementation with Maple and Magma's serial implementations of Zippel's GCD algorithm.