Exploiting unconventional QR-algorithms for fast and accurate computations of roots of polynomials
Final Report Abstract
Computing roots of polynomials is an important historical mathematical problem as, e.g., already the Babylonians, 4000 years ago, were computing roots of polynomials of degree two. Past investigations furnished us a whole range of root-solvers; thousands are available nowadays. Most of these methods were designed for low degree polynomials (less than 20) originating from applications in financing, coding theory, engineering, statistics and so on. Research evolutions, however, brought us new applications and larger problems from, e.g., algebraic optimization, algebraic geometry, signal processing, financing, particular ordinary differential equations, and control theory, all requiring the solution of polynomials having degrees of several thousands. The roots of a polynomial are identical to the eigenvalues of the companion matrix. Some modern root solvers use the QR algorithm, one of the top 10 algorithms of the 20th century, to compute the eigenvalues of the companion matrix. In state-of-the-art software packages, e.g., in LAPACK, the special structure of the companion matrix is ignored. The consequence is that the algorilhm requires π^3 time and storage, while π^2 time and n storage should be sufficient. There, however, exist numerical algorithms that exploit the structure and solve the problem in operations. These QR algorithms use a data-sparse representation of the companion matrix and the iterates of the QR algorithm. However, the algorithms have to enforce the data-sparse structure of the iterates from time to time and often suffer from a loss of accuracy. They are faster but less accurate than the LAPACK implementation. We were able to find a new factorized representation of the companion matrix and the iterates of the QR algorithm that requires explicit computations, comparable to structure enforcement, only in the first five iterations. This led to a new QR algorithm for companion matrices which is about four limes faster than the fastest state-of-the-art algorithms and as accurate as the LAPACK implementation.
Publications
- Computing approximate extended Krylov subspaces without explicit inversion. Electronic Transactions on Numerical Analysis, 2013; available as KU Leuven Department of Computer Science Report TW623; 22 pages
Thomas Mach, Miroslav S. Pranic, and Raf Vandebril
- On deflations in extended QR algorithms. Department of Computer Science Report TW 634, KU Leuven, 2013; 20 pages
Thomas Mach and Raf Vandebril
