Quasi-GCD computations

For univariate polynomials with real or complex coefficients and a given error bound ? > 0, h is called a quasi-gcd of f and g, if h is an ?-approximate divisor of f and of g and if any (exact) common divisor of f, g is an approximate divisor of h. Extended quasi-gcd computation means to find such h and additional cofactors u, ν such that | uf + νg ? h | < ? | h | holds. Suitable “pivoting” leads to a numerically stable version of Euclid's algorithm for solving this task. Further refinements by a divide-and-conquer technique and by means of fast algorithms for polynomial arithmetic then yield the worst case upper bound O(n² lg n(lg(1/?) + n lg n)) of “pointer time” for nth-degree polynomials. In the particular case of integer polynomials, however, an immediate reduction to fast integer gcd computation is recommended, instead.