Nearly Optimal Black Box Polynomial Root-finders

Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our novel nearly optimal Las Vegas randomized root-finders approximate all zeros of a polynomial almost as fast as one accesses its coefficients with the precision required for the solution within a prescribed error bound.1 Moreover, our root-finders can be applied to a black box polynomial, defined by an oracle (that is, black box subroutine) for its evaluation rather than by its coefficients. Such root-finders are particularly fast for polynomials that can be evaluated fast, e.g., the sum of a few shifted monomials, but the only other known black box root-finder is the pioneering one by Louis and Vempala at FOCS 2016, and it only approximates the absolutely largest root of a real-rooted polynomial. Our deterministic divide and conquer algorithm of ACM STOC 1995 is the only other known nearly optimal polynomial root-finder, and it extensively uses the coefficients, is quite involved, and has never been implemented, while according to extensive numerical experiments with standard test polynomials, already initial implementations of our new root-finders compete with user's choice package of root-finding subroutine MPSolve and supersede it more and more significantly where the degree of a polynomial grows large. Our root-finders are readily extended to support approximation of the eigenvalues of a matrix within a record Las Vegas expected bit operation time bound. Our auxiliary algorithms and techniques for computations with black box polynomials can be of independent interest.