# Polynomial GCD in the presence of floating-point errors

The crucial requirement for using root isolation methods based on Vincent's theorem is that the input polynomial does not have multiple zeros. One way to remove the multiple zeros is to use polynomial GCD. However, when it is implemented with the usual floating-point numbers (IEEE doubles), most probably the various rounding errors will cause the multiple roots to disintegrate into clusters of roots.

Does anyone know about good (and simple) approximate polynomial GCD algorithm, which does not require exact arithmetic (i.e. is amenable to implementation in 64-bits floating points numbers)?

The closest thing I found is the "Computing multiple roots of inexact polynomials" by Zhonggang Zeng but unfortunately it is way over my tiny brain.

• What would " approximate polynomial GCD" mean? – lhf Jul 27 '15 at 18:06
• I doubt there exists one. Commercial software such as Maple and Mathematica use exact arithmetic in their root finding packages (Regular Chains package in Maple and Reduce in Mathematica). – Sergio Parreiras Jul 27 '15 at 18:11
• @lhf By "approximate" I meant an algorithm which is able to split the polynomial even if the coefficients are in, and computation is done in, floating point. (Yes, one can represent 53 bits integers exactly in doubles - what I meant is the various over-/under-flows when calculating with floats) – Ecir Hana Jul 27 '15 at 18:19

• Along with the floating-point version of the polynomial GCD (possibly in interval arithmetic), compute the GCD modulo some prime(s) (I assume your input consists of polynomials in $\mathbb{Q}[x]$). Not only that this will, with high probability, give you the correct degree of the GCD; unless you have chosen an "unlucky" prime, the sequence of the degrees and coefficients occuring throughout the EEA should be identical modulo the prime. So you can use these results as a sanity check for any rounding to or away from zero.