There are two different ways to get a set of linearly independent
eigenvectors to a multiple eigenvalue. The first is to restart and run
a projected operator on the subspace orthogonal to the converged
eigenvector(s), where all the converged eigendirections have
been projected away. This corresponds to orthogonalizing the vector
in step (9) of Algorithm 4.6
to all converged eigenvectors. This procedure is repeated as long as
new vectors converge; see, e.g., [318].
There is a second, more radical way to deal with possibly multiple
eigenvalues: the block Lanczos method. It starts with several, say
,
starting directions, forming a block
, and lets
operate on all of
in step
, to compute a new orthogonal block
. The
matrix
will be a block-tridiagonal, or more properly band matrix;
see the description in §4.6.
In the block Lanczos method, the convergence is governed by the separation of the
desired eigenvalue from other
eigenvalues
away in the spectrum, say
, if we assume the
eigenvalues sorted from smallest to largest. However, the degree of the
polynomial is
, not
, as we would have if we ran single-vector
Lanczos for the same number of basis vectors, and this will slow down
the convergence in the general case.
Regardless of the above objection, block Lanczos is advantageous for efficiency reasons, whenever
computing for an
matrix
is much cheaper than
computing
for
vectors, one after the other. This is
the case for most machines with cache memories and when the matrices are so
large that they need to be stored in secondary storage.