  Univariate polynomial root-finding has been studied for four millennia and
very intensively in the last decades. Our new near-optimal root-finders
approximate all zeros of a polynomial p almost as fast as one accesses its
coefficients with the precision required for the solution within a prescribed
error bound. Furthermore, our root-finders can be applied to a black box
polynomial, defined by an oracle (black box subroutine) for its evaluation
rather than by its coefficients. Due to this feature our root-finders support
approximation of the eigenvalues of a matrix in a record Las Vegas expected bit
operation time and are particularly fast for a polynomial that can be evaluated
fast such as the sum of a few shifted monomials or a Mandelbrot-like polynomial
defined by a recurrence. Our divide and conquer algorithm of ACM STOC 1995 is
the only other known near-optimal polynomial root-finder, but it extensively
uses the coefficients, is quite involved, and has never been implemented, while
according to extensive numerical experiments with standard test polynomials,
already a slower initial implementation of our new root-finders competes with
user's choice package of root-finding subroutines MPSolve and supersedes it
more and more significantly as the degree of a polynomial grows large. We
elaborate upon the design and analysis of our algorithms, comment on their
potential heuristic acceleration, and briefly cover polynomial root-finding by
means of functional iterations. Our techniques can be of independent interest.
