New Fast Polynomial Root-Finders

Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our {\em black box root-finder} involves no coefficients and works for a black box polynomial, defined by an oracle (that is, black box subroutine) for its evaluation. Such root-finders have various benefits, e.g., are particularly efficient where a polynomial can be evaluated fast, say, is a sum of a small number of shifted monomials (x-c)^a. Our root-finder approximates all d complex zeros of a dth degree polynomial p(x) (aka roots of equation p(x)=0) by using Las Vegas expected number of bit-operations within a factor of b of the theoretical lower bound. When extended with disc compression techniques to get an acceleration by a factor of b/\log(b), the algorithm achieves near-optimal complexity. That is, the resulting root-finder is expected to run almost as fast as one accesses the coefficients with a precision required for the solution within a prescribed error bound. We also introduce an algorithm for DLG root-squaring that circumvents the classical numerical instability of the recursive iterations. By applying root-squaring to Newton's Inverse Ratios rather than coefficients, we enable the fast estimation of extremal root radii for black box polynomials. This technique provides a highly efficient exclusion test for determining whether a fixed disc on the complex plane contains any roots. Historically the only known near-optimal polynomial root-finder was presented by V. Pan at ACM STOC 1995. It is quite involved and has never been implemented, while already in its initial implementation our new root-finder competed with user's choice package of root-finding subroutines MPSolve, according to extensive numerical experiments with standard test polynomials. Furthermore we readily extend our black box root-finder to approximation of the eigenvalues of a matrix in record expected bit operation time, which is an extension not supported by the root-finder of STOC 1995. More recently, the framework for reaching the theoretical lower bound for polynomial root-finding was further advanced by V. Pan at SODA 2024, providing the basis for the near-optimal extension of our work via disc compression.