A Fast Algorithm for Approximate Polynomial GCD Based on Structured Matrix Computations
Dario A. Bini, Paola Boito · Birkhäuser Basel eBooks · 2010
An O(n 2) complexity algorithm for computing an ∈-greatest common divisor (gcd) of two polynomials of degree at most n is presented. The algorithm is based on the formulation of polynomial gcd given in terms of resultant (Bézout, Sylvester) matrices, on their displacement structure and on the reduction of displacement structured matrices to Cauchy-like form originally pointed out by Georg Heinig. A Matlab implementation is provided. Numerical experiments performed with a wide variety of test problems, show the effectiveness of this algorithm in terms of speed, stability and robustness, together with its better reliability with respect to the available software.