Certified approximate univariate GCDs (Q1358910)

The paper deals with computing the approximate greatest common divisor (GCD) of two univariate polynomials given with limited accuracy. The authors provide a counterexample to the direct approach which relies only on the Sylvester matrix singular values and on the extended Euclidean algorithm. It is concluded that Euclid's algorithm is unable to find the maximum-degree GCD polynomial within some guaranteed error. The authors use a direct algebraic approach to prove a gap theorem on the singular values of the subresultant matrices that guarantees the degree for the approximate GCD.