Nearly Optimal Algorithms for Univariate Polynomial Factorization and Rootfinding. II: Computing a Basic Annulus for Splitting

We describe some effective algorithms for the computation of a basic well isolated annulus over which we split a given univariate $n$th degree polynomial numerically into two factors. This is extended to recursive computation of the complete numerical factorization of a polynomial into the product of its linear factors and further to the approximation of its roots. The extension incorporates the earlier techniques of Schönhage and Kirrinnis and our old and new splitting techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the complexity of both complete factorization and rootfinding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of $n$ for complete factorization and also for the approximation of well-conditioned (well isolated) roots.