Optimization strategies for the approximate GCD problem

Abstract

We describe algorithms for computing the greatest common divisor (GCD) of two univariate polynomials with inexactlyknown coefficients. Assuming that an estimate for the GCD degree is available (e.g., using an SVD-based algorithm), we formulate and solve a nonlinear optimization problem in order to determine the coefficients of the "best" GCD. We discuss various issues related to the implementation of the algorithms and present some preliminary test results.