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.