Joseph
Haraldson,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
The polynomial Approximate Greatest Common Divisor (GCD) problem consists of given two polynomials, find a pair of nearby polynomials having a non-trivial GCD. This talk discusses the problem of how to approximate an exact GCD numerically to arbitrarily high precision and optimization approaches to compute nearby polynomials with a non-trivial GCD.
Classical approximate GCD techniques rely on the singular value decomposition and QR factorization, which are generally suitable for initial guesses to optimization routines. The existence and uniqueness of solutions to the problem is reviewed and presented in the context of optimization algorithms based on gradient and Newton methods. A large portion of the talk discusses the polynomial time algorithm of Karmarkar and Lakshman that is able to solve the simplest variant of the approximate GCD problem using variable projection.