  The recent subdivision algorithms for univariate polynomial Complex Root
Clustering (CRC) and Real Root Isolation (RRI) approximate all roots in a fixed
Region of Interest (RoI) and, like the algorithm of Pan (1995, 2002), achieve
near optimal bit complexity for the so called benchmark problem. On the other
hand, user's current choice for the approximation of all complex roots of a
polynomial is the package MPSolve, implementing Ehrlich -- Aberth's iterations.
Their very fast empirical global convergence (right from the start) is
well-known although has no formal support. Subdivision iterations allow robust
implementations, one of which is currently the user's choice for solving the
RRI problem, including the task of the approximation of all real roots. Another
implementation is slower than MPSolve (by several orders of magnitude) for
finding all roots but outperforms MPSolve for solving the CRC problem where the
RoI contains only a small number of roots. We analyze and extend a 2000 variant
of Sch\"onhage's algorithm of (1982), which efficiently computes narrow real
intervals that contain the moduli of all roots, thus defining a set of annuli
covering all the complex roots. We present an implementable version of this
algorithm and by using the computed sets of annuli improve in practice
subdivision algorithms for CRC and RRI while supporting near optimal bit
complexity.
