|
Zippel's algorithm for the non-monic 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 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 various approaches for handling the non-monic case, in particular, a normalization technique and a method which uses a sparse rational function interpolation algorithm. |