A stable algorithm to compute the roots of polynomials is presented. The roots are found by
computing the eigenvalues of the associated companion matrix by Francis's implicitly shifted
QR algorithm. A companion matrix is an upper Hessenberg matrix that is unitary-plus-rank-
one, that is, it is the sum of a unitary matrix and a rank-one matrix. These properties are
preserved by iterations of Francis's algorithm, and it is these properties that are exploited
here. The matrix is represented as a product of 3n-1 Givens rotators plus the rank-one part …

This work is a continuation of work by JL Aurentz, T. Mach, R. Vandebril, and DS Watkins, J.
Matrix Anal. Appl., 36 (2015), pp. 942--973. In that paper we introduced a companion QR
algorithm that finds the roots of a polynomial by computing the eigenvalues of the
companion matrix in O(n^2) time using O(n) memory. We proved that the method is
backward stable. Here we introduce, as an alternative, a companion QZ algorithm that
solves a generalized eigenvalue problem for a companion pencil. More importantly, we …