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. © 2013 Society for Industrial and Applied Mathematics.