Date: Giovedi' 9 Aprile Time: 11:00 Place: Aula Seminari, dipartimento di matematica
Speaker: Raf Vandebril, Department of Computer Science, KU Leuven.
Title: *The Companion QR*
Abstract: In this lecture we will propose a new fast and stable manner of computing roots of polynomials. Roots of polynomials are typically computed by putting the coefficients of the polynomial in the companion matrix and then computing the eigenvalues of this matrix. Exploiting the available low-rank structure leads to an algorithm of quadratic instead of cubic complexity.
Several low-cost algorithms have already been proposed. Either they fully exploit the low-rank properties of the involved matrices by representing them for instance via quasiseparable factors, or they write the companion matrix as the sum of a unitary plus low rank matrix and exploit this structure.
In this lecture we will use the second manner. However, only a single QR step requires the use of the low rank part. After that we can put the low rank term aside and continue only with the unitary matrix, translating the problem thereby to a unitary eigenvalue problem. Only in the end the low rank matrix is reconstructed to retrieve the eigenvalues.
Numerical experiments validate the approach, illustrate its reliability and speed. The algorithm is compared against other available methods and a proof of backward stability is provided.
This research is joint work with David S.\ Watkins and Jared L.\ Aurentz from Washington State University, USA and Thomas Mach from the KU Leuven, Belgium.
===
Everyone is welcome!