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