CERTIFIED APPROXIMATE UNIVARIATE GCDS

We study the approximate GCD of two univariate polynomials given with limited accuracy or, equivalently, the exact GCD of the perturbed poly nomials within some prescribed tolerance. A perturbed polynomial is re garded as a family of polynomials in a classification space, which lea ds to an accurate analysis of the computation. Considering only the Sy lvester matrix singular values, as is frequently suggested in the lite rature, does not suffice to solve the problem completely, even when th e extended euclidean algorithm is also used. We provide a counterexamp le that illustrates this claim and indicates the problem's hardness. S VD computations on subresultant matrices lead to upper bounds on the d egree of the approximate GCD. Further use of the subresultant matrices singular values yields an approximate syzygy of the given polynomials , which is used to establish a gap theorem on certain singular values that certifies the maximum-degree approximate GCD. This approach leads directly to an algorithm for computing the approximate GCD polynomial . Lastly, we suggest the use of weighted norms in order to sharpen the theorem's conditions in a more intrinsic context. (C) 1997 Elsevier S cience B.V.