Topics in Comptuter Algebra: IV

Multivariate polynomial GCD computation.

Michael Monagan, Department of Mathematics, Simon Fraser University.

Wednesday June 17th and July 8th, 2009, K9509, 3:30-5:00pm.

We will present Brown's dense modular GCD algorithm from 1971
and Zippel's sparse modular GCD algorithm from 1979.

For a prime p, Brown's algorithm recursively interpolates the gcd G of
A and B in Zp[x1,...xn] from images in
in one less variable using a dense interpolation.
If the gcd G is sparse in many variables, e.g., G = x1^d + x2^d + ... + xn^n + 1,
this interpolation requires at least (n-1)^(d+1) univariate images
in Zp[x1], which is exponential in n, the number of variables.
In comparison, Zippel's sparse interpolation reduces this to O(n^2d).

Zippel's algorithm is one of the first probabilistic algorithms.
A variation of it called LINZIP by de Kleine, Monagan and Wittkopf (2005)
is now being used in Maple.