Raf Vandebril
KU Leuven, Belgium
Fast and Stable Roots of Polynomials via Companion Matrices
6 February 2024, 5pm
KU Leuven, Aula Arenbergkasteel (01.07)
Streaming: https://eu.bbcollab.com/guest/99583fe6bbe145bfb9f346f35f32450f
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
