Structured Low Rank Approximation of a Bezout Matrix

The task of determining the approximate greatest common divisor (GCD) of more than two univariate polynomials with inexact coefficients can be formulated as computing for a given Bezout matrix a new Bezout matrix of lower rank whose entries are near the corresponding entries of that input matrix. We present an algorithm based on a version of structured nonlinear total least squares (SNTLS) method for computing approximate GCD and demonstrate the practical performance of our algorithm on a diverse set of univariate polynomials. The work is partially supported by a National Key Basic Research Project of China 2004CB318000 and Chinese National Science Foundation under Grant 10401035.