Fast Computation of the Zeros of a Polynomial via Factorization of the Companion Matrix

Abstract

A new fast algorithm for computing the zeros of a polynomial in $O(n^{2})$ time using $O(n)$ memory is developed. The eigenvalues of the Frobenius companion matrix are computed by applying a nonunitary analogue of Francis's implicitly shifted $QR$ algorithm to a factored form of the matrix. The algorithm achieves high speed and low memory use by preserving the factored form. It also provides a residual and an error estimate for each root. Numerical tests confirm the high speed of the algorithm.