Fast and Stable Roots of Polynomials via Companion Matrices
Raf Vandebril presents 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.
Practical information:
Georganiseerd door:
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
Teacher / speaker
I am a professor at the KU Leuven, Department of Computer Science.
Since 2022, I am the head of research unit NUMA -- Numerical Analysis and Applied Mathematics. In the academic year 2022-2023 I was the chair of the Doctoral Committee of the Faculty of Engineering Science, part of the Arenberg Doctoral School.
Back to the Roots Seminar Series
The ERC research project "Back to the roots of data-driven dynamical system identification", led by Prof. Dr. Bart De Moor (KU Leuven, ESAT-STADIUS), focuses on system identification, where mathematical models are derived from observed data generated by systems such as medical monitoring, electricity consumption and industrial processes. Utilizing optimization algorithms, one seeks to identify the best model in a chosen model class. This methodology finds widespread application across thousands of use cases within the AI community. However, there is no guarantee that optimization algorithms will find the best model. Present-day optimization practices are heuristic in nature, yielding results that may not be reproducible and consequently difficult to interpret.
The main objective of the Back to the Roots project is to develop a theoretical framework that combines model classes and optimization algorithms, enabling the calculation of the optimal model within the specified model class with 100% certainty.
