Structured matrix-based methods for polynomial ∈-gcd
Dario A. Bini, Paola Boito · 2007
The relationship between univariate polynomial ∈-gcd and factorization of resultant matrices is investigated and several stable and effective algorithms for the computation of an ∈-gcd are proposed. The main result is the design of a practically stable algorithm whose arithmetic cost is quadratic in the degrees of the input polynomials. The algorithm relies on the displacement structure properties of Sylvester and Bezout matrices. Its effectiveness is confirmed by numerical experiments.