Pole Swapping Methods for the Eigenvalue Problem - Rational QR Algorithms

The matrix eigenvalue problem is often encountered in scientific computing applications. Although it has an uncomplicated problem formulation, the best numerical algorithms devised to solve it are far from obvious. Computing all eigenvalues of a small to medium-sized matrix is nowadays a routine task for an algorithm of implicit QR-type using a bulge chasing technique. On the other hand projection methods are often used to compute a subset of the eigenvalues of sparse, large-scale eigenproblems. Krylov subspace methods are probably among the most used methods within this class. The convergence of the classical implicit QR and Krylov subspace methods is determined by polynomials. The lion's share of this thesis is concerned with QR-type methods whose convergence is governed by the more general class of rational functions. The first numerical scheme we present is the rational QZ method for the generalized eigenvalue problem. It uses a pole swapping technique on Hessenberg pencils. We provide an implicit Q theorem for Hessenberg pencils which motivates the pole swapping approach as it shows that the rational QZ iterates are unique. Rational Krylov theory allows us to prove that the rational QZ method implicitly performs subspace iteration accelerated by rational functions. Numerical experiments exemplify that novel rational shifting strategies significantly reduce the computational cost compared to their polynomial counterparts. Furthermore, we propose a novel reduction algorithm to Hessenberg form and show that premature middle deflations can already be induced during the reduction phase provided a good choice of poles is made. In the subsequent chapter recent developments for polynomial QR-type methods are adapted to the rational QZ method. This results in a multishift, multipole rational QZ method with tightly-packed shifts and poles. Aggressive early deflation is included to detect converged eigenvalues before classical deflation criteria are able to do so. Our implementation is made publicly available and numerical experiments demonstrate that it outperforms LAPACK in terms of accuracy, speed and empiric time complexity. A rational QR method is proposed as a specification of the rational QZ method which treats the standard eigenvalue problem in an efficient manner. This method applies a pole swapping algorithm on Hessenberg, unitary Hessenberg pencils where only O(n) storage space is required for the unitary matrix. Consequently, the storage requirements and computational cost is approximately halve of the rational QZ method. Two-sided pole swapping algorithms for tridiagonal pencils are studied in the penultimate chapter. These result in the rational LR algorithm for unsymmetric pencils and the rational TTT algorithm for symmetric, diagonalizable pencils. These algorithms have a reduced computational cost of O(n 2 ) thanks to the tridiagonal structure but employ non-unitary equivalence transformations such that numerical stability is no longer guaranteed. We provide optimality results for the non-unitary transformations. Numerical experiments show promising results but also show that numerical stability is nontrivial. The last chapter of the thesis considers the well-known rational Krylov method for the solution of large-scale eigenproblems. We show how eigenvalue estimates obtained with the rational Krylov method can be computed with the rational QZ method. Furthermore, we test the pole swapping technique to efficiently filter and restart the rational Krylov method.status: publishe