ERC Back to the Roots Seminar by Prof. Raf Vandebril

Fast and Stable Roots of Polynomials via Companion Matrices

Start: 6/02/2024, 17:00
Location: Aula Arenbergkasteel

Abstract

We present a fast and stable algorithm for computing roots of polynomials. 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 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) flops per iteration and thus O(n²) 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²) methods that have been proposed, and its accuracy is comparable or better.

The paper accompanying this research received SIAM’s outstanding paper prize in 2017.
https://www.siam.org/prizes-recognition/major-prizes-lectures/detail/siam-outstanding-paper-prizes

Organized by: Bart De Moor