Numerical methods for computing the greatest common divisor of univariate polynomials using floating point arithmetic

Abstract

Computing the greatest common divisor (GCD) for two polynomials in floating point arithmetic is computationally challenging and even standard library software might return the result GCD=1 even when the polynomials have a nontrivial GCD. Here we review Euclid's algorithm and test a variant for a class of random polynomials. We find that our variant of Euclid's method often produces an acceptable result. However, close monitoring of the norm of the vector of coefficients of the intermediate polynomials is required. References

• R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt. The singular value decomposition for polynomial systems. In Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC '95, pages 195–207. ACM, 1995. doi:10.1145/220346.220371.
• H. J. Stetter. Numerical polynomial algebra. SIAM, 2004. doi:10.1137/1.9780898717976.
• Z. Zeng. The numerical greatest common divisor of univariate polynomials. In Randomization, relaxation, and complexity in polynomial equation solving, volume 556 of Contemp. Math., pages 187–217. Amer. Math. Soc., 2011. doi:10.1090/conm/556/11014.