Fast and Stable Roots of Polynomials via Companion Matrices

The talk is based on the paper which won SIAM’s outstanding Paper Prize in 2017.

In this talk a fast and stable algorithm for computing roots of polynomials will be presented. The 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-shifted QR algorithm this property is preserved, and exactly that is exploited here.

To compactly store the matrix it will be shown that only 3n-1 rotators are required, so the storage space is O(n). In fact, these rotators only represent the unitary part, but it will be shown 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) flops per iteration and thus O(n^2) flops in total. The 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(n^2) methods that have been proposed, and its accuracy is comparable or better.