A fast parallel sparse polynomial GCD algorithm (Q1994882): Difference between revisions

This work introduces a parallel modular GCD algorithm for sparse multivariate polynomials with integer coefficients. The computation of the GCD of multivariate polynomials is known as an important problem in symbolic computation and has been studied by many authors. The bottleneck in this problem was always the growth of the coefficients through the computations until modular algorithms appeared in the 70s, which are really efficient for sparse polynomials. In this work, the authors combine a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. Throughout the article, they explain in detail the strengths (fast, highly parallelizable) and weaknesses (existence of unlucky homomorphisms, that is, unlucky evaluation points) of their methodology. They also compare their implementation with the serial implementations they have done of Zippel's GCD algorithm in Maple and Magma.