The approximate irreducible factorization of a univariate polynomial
Zhonggang Zeng · 2009
When multiple roots are present, factoring a univariate polynomial is an ill-posed problem in the sense that it is highly sensitive to data perturbations and the round-off error. In ISSAC '03, the author introduced an algorithm that is capable of calculating the polynomial roots and multiplicities accurately using floating point arithmetic without extending the hardware precision even if the coefficients are perturbed. This paper revisits the problem by establishing a rigorous theoretical framework for eliminating the ill-posedness and by introducing a redesigned algorithm. The new algorithm avoids error accumulation in the GCD computation and substantially improves the accuracy and robustness.