A matrix QR-factorization approach to common factor extraction in the noisy data case

摘要

The obvious approach to computing the common factor (i.e., greatest common divisor (GCD)) between polynomials over a real number field is to employ Euclid's algorithm. However, this algorithm is not robust if the polynomial coefficients are perturbed by noise. Here we see that GCD computation is equivalent to QR-factorizing a rank deficient near-to-Toeplitz matrix derived from the Sylvester matrix of the polynomials. Given noisy data the matrix is only nearly rank deficient. We summarize a computationally efficient and numerically reliable algorithm for QR-factorizing the nearly rank deficient matrix.