Rational Krylov Subspace Method

The rational Krylov subspace method computes eigenvalues and eigenvectors of
a regular pencil,

Rational Krylov starts as a shifted and inverted Arnoldi iteration
with shift and starting vector . It computes an
orthonormal basis using the basic recursion,

and get the Ritz values and Ritz vectors for . We get good approximations after a moderate number of steps to those eigenvalues that are closest to the shift .

Now the idea behind the rational Krylov algorithm is to continue with
a *new* shift , when we want to get approximations to
the eigenvalues close to that new shift. The tricky thing is to avoid
throwing away all the information gathered in the basis ,
computed using the old shift . This is indeed possible if
we replace the basis with a new basis , which spans
the same subspace as but can be interpreted as the
orthogonal basis of an Arnoldi recursion (8.18) with the
new shift . At the same time the trapezoidal (Hessenberg)
matrix is replaced by a new matrix of the same form,
.

Rewrite the recursion (8.18) as

Add a matrix to the left-hand side, so that is replaced by the new shift in the right-hand side,

and note that is the only large matrix in the left-hand side,

The matrix in the left-hand side is trapezoidal with the same pattern of nonzeros as , and we may come back to an expression similar to the recursion (8.18) by premultiplying with to get

It remains to get rid of the factor on the left-hand side,
and this is done in the following way. Make a QR decomposition
of and get

Multiply from the right with the inverse of the triangular matrix , which we know is nonsingular if the Hessenberg matrix is unreduced,

Introduce the new orthogonal basis and note that the pencil (8.17) is represented by the full matrix,

in this new basis. We may transform this into trapezoidal (upper Hessenberg) form by applying the Householder algorithm from the bottom upwards (see [377]),

Multiply the recursion (8.20) by the orthogonal from the right and get

or

an Arnoldi recursion (8.18) with the new shift , the new orthogonal basis,

and the new trapezoidal (upper Hessenberg) matrix .

We once again stress that all these transformations are effected without actually performing any operations on the large matrices and . We may even accumulate all the and factors and avoid forming explicitly, thus avoiding all extra work on long vectors. Also note that even if we get an Arnoldi recursion, it does not start at the original starting vector but at , which is a linear combination of all the vectors computed during the whole rational Krylov algorithm.

In a practical implementation, this is combined with locking,
purging, and implicit restart. First run shifted and inverted Arnoldi
with the first shift . When an appropriate number
of eigenvalues around have converged, say after steps,
lock these converged eigenvalues
and purge those that are altogether outside the interesting
region, leaving a -step Arnoldi recursion (8.18).
Then introduce the new shift and follow
the description in this section to get a new basis which
replaces .
Start at the new shift by operating on the last vector of this new basis

and get the next basis vector in the Arnoldi recursion (8.18) with the new shift . Continue until we get convergence for a set of eigenvalues around , and repeat the same procedure with new shifts until either all interesting eigenvalues have converged or all the shifts in the prescribed frequency range have been used.

Notice that in step (3) we make just operations with the shifted and inverted matrix, the first basis vectors are those saved from the previous shift . The lock, purge, and deflation operations in step (4) are very similar to those for implicitly restarted Arnoldi as described in §7.6; we have actually used a nonhermitian version of thick restart [463]. In step (5) we choose the new shift as a value in the complex plane where we are interested in studying the behavior of the matrix pencil (8.17). However, a choice too close to an eigenvalue will result in a nearly singular matrix . Moreover, a new shift at a nearly converged Ritz value will make the upper triangular factor in step (6) close to singular.

When the second matrix in the original pencil (8.17) is positive definite, we may choose to make the basis orthogonal. If then is also Hermitian, so is , and we may work with tridiagonal matrices; see [322].

This formulation of rational Krylov is different from the one used earlier [378], where the same set of basis vectors is used throughout and the pencil (8.17) is transformed into two Hessenberg matrices. We have found that this new formulation gives a more natural way to continue with a new shift and signal when we risk losing accuracy due to linear dependence.

See the report [379] for a numerical example from model reduction.