  Univariate polynomial root-finding is a classical subject, still important
for modern computing. Frequently one seeks just the real roots of a polynomial
with real coefficients. They can be approximated at a low computational cost if
the polynomial has no nonreal roots, but for high degree polynomials, nonreal
roots are typically much more numerous than the real ones. The challenge is
known for a long time, and the subject has been intensively studied.
Nevertheless, we produce some novel ideas and techniques and obtain dramatic
acceleration of the known algorithms. In order to achieve our progress we
exploit the correlation between the computations with matrices and polynomials,
randomized matrix computations, and complex plane geometry, extend the
techniques of the matrix sign iterations, and use the structure of the
companion matrix of the input polynomial. The results of our extensive tests
with benchmark polynomials and random matrices are quite encouraging. In
particular in our tests the number of iterations required for convergence of
our algorithms grew very slowly (if at all) as we increased the degree of the
univariate input polynomials and the dimension of the input matrices from 64 to
1024.
