## Project

# 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.