Polynomial Root Finding Using Iterated Eigenvalue Computation

We present a novel iterative algorithm that approximates all roots of a univariate polynomial. The iteration uses floating-point eigenvalue computation of a generalized companion matrix. With some assumptions, we show that the algorithm approximates the roots to floating-point accuracy within about log sub (rho/epsilon) khi(P) iterations, where epsilon is the relative error of floating-point arithmetic, rho is the relative separation of the roots, and khi(P) is the condition number o of the polynomial. Each iteration requires an nxn floating-point eigenvalue computation, n the polynomial degree, and evaluation of the polynomial to floating-point accuracy at n points. On some hard examples of ill-conditioned polynomials, e.g., high-degree Wilkinson polynomials, a careful implementation of the algorithm is an order of magnitude faster than the best alternative.