Fast and Stable Roots of Polynomials via Companion Matrices

In this talk we present a fast and stable algorithm for computing roots of polynomials. e roots are found by computing the eigenvalues of the associated companion matrix. A companion matrix is an upper Hessenberg matrix that is of unitary–plus–rank–one form, that is, it is the sum of a unitary matrix and a rank–one matrix. When running Francis’s implicitly–shi ed QR algorithm this property is preserved, and exactly that is exploited here. To compactly store the matrix we will show that only 3n − 1 rotators are required, so the storage space is O(n). In fact, these rotators only represent the unitary part, but we will show that we can retrieve the rank-one part from the unitary part with a trick. It is thus not necessary to store the rank-one part explicitly. Francis’s algorithm tuned for working on this representation requires only O(n) ops per iteration and thus O(n2) ops in total. e algorithm is normwise backward stable and is shown to be about as accurate as the (slow) Francis QR algorithm applied to the companion matrix without exploiting the structure. It is also faster than other O(n2) methods that have been proposed, and its accuracy is comparable or be er.status: publishe