
Zippel's algorithm for the nonmonic caseJennifer de Kleine, MITACSMonday March 29th, 2004 in K9509 at 3:30pm.
Abstract: The sparse modular GCD algorithm was presented by Zippel for computing the greatest common divisor of two multivariate polynomials over the integers. We extend this algorithm to work for nonmonic GCDs. The nonmonic 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 nonmonic 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 various approaches for handling the nonmonic case, in particular, a normalization technique and a method which uses a sparse rational function interpolation algorithm. 