Zippel's algorithm for the non-monic case

Jennifer de Kleine, MITACS

Monday 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.