Zippel's Algorithm Extended for the Non-Monic Case.
The sparse modular GCD algorithm was presented by Richard Zippel for computing the greatest common divisor of two multivariate polynomials over the integers. It improves the efficiency of Brown's algorithm when the gcd is sparse. We extend this algorithm to work for non-monic GCDs.
The non-monic case occurs when the GCD has a leading coefficient involving one or more variables. For example, the GCD G = (4y+2z)x^2 + 7 in Z[x,y,z] is non-monic in the main variable x. The problem is that at the bottom level of our algorithm we call the Euclidean algorithm, which returns a monic GCD. We describe two different approaches for handling the non-monic case. One involves solving a sequence of large structured linear systems. The other method uses a sparse rational function interpolation algorithm.