QR-factorization method for computing the greatest common divisor of polynomials with inexact coefficients

This paper presents a novel means of computing the greatest common divisor (GCD) of two polynomials with real-valued coefficients that have been pertu rbed by noise. The method involves the QR-factorization of a near-to-Toepli tz matrix derived from the Sylvester matrix of the two polynomials. It turn s out that the GCD to within a constant factor is contained in the last non zero row of the upper triangular matrix R in the QR-factorization of the ne ar-to-Toeplitz matrix. The QR-factorization is efficiently performed by an algorithm due to Chun ef al. A condition number estimator due to Bischof an d an algorithm for rank estimation due to Zarowski are employed to account for the effects of noise.