Real Polynomial Root-finding: New Advances

(Supported by NSF Grant CCF 1116736) Abstract. Univariate polynomial root-finding is both classical and im-portant 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 typ-ically nonreal roots are much more numerous than the real ones. We dramatically accelerate the known algorithms in this case by exploiting the correlation between the computations with matrices and polynomi-als, extending the techniques of the matrix sign iteration, and exploiting the structure of the companion matrix of the input polynomial