  We approximate the d complex zeros of a univariate polynomial p(x) of a
degree d or those zeros that lie in a fixed region of interest on the complex
plane such as a disc or a square. Our divide and conquer algorithm of STOC 1995
supports solution of this problem in optimal Boolean time (up to a
poly-logarithmic factor), that is, runs nearly as fast as one can access the
coefficients of p with the precision necessary to support required accuracy of
the output. That record complexity has not been matched by any other algorithm
yet, but our root-finder of 1995 is quite involved and has never been
implemented. We present alternative nearly optimal root-finders based on our
novel variants of the classical subdivision iterations. Unlike our predecessor
of 1995, we require randomization of Las Vegas type, allowing us to detect any
output error at a dominated computational cost, but our new root-finders are
much simpler to implement than their predecessor of 1995. According to the
results of extensive test with standard test polynomials for their preliminary
version, which incorporates only a part of our novel techniques, the new
root-finders compete and for a large class of inputs significantly supersedes
the package of root-finding subroutines MPSolve, which for decades has been
user's choice package. Unlike our predecessor of 1995 and all known fast
algorithms for the cited tasks of polynomial root-finding, our new algorithms
can be also applied to a polynomial given by a black box oracle for its
evaluation rather than by its coefficients. This makes our root-finders
particularly efficient for polynomials p(x) that can be evaluated fast such as
the Mandelbrot polynomials or those given by the sum of a small number of
shifted monomials. Our algorithm can be readily extended to fast approximation
of the eigenvalues of a matrix or a matrix polynomial.
