Quasi-gcd computations (Q1071503): Difference between revisions

For univariate polynomials with real or complex coefficients and a given error bound \(\epsilon >0\), h is called a quasi-gcd of f and g, if h is an \(\epsilon\)-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, v such that \(| uf+vg-h| <\epsilon | 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^ 2lg n(lg(1/\epsilon)+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.