A band Lanczos method for Hermitian matrices was first
proposed in [375].
The Hermitian band Lanczos Algorithm 4.12 described
here, however, is somewhat different in that it uses both the
first Lanczos vectors (4.28) and the
candidate vectors (4.30) for the following
Lanczos
vectors.
This makes it possible to build only the
matrix
.
The algorithm in [375] constructs the first
Lanczos vectors, and as a result, it needs to build a somewhat
larger
matrix, instead of
.
The version of the band Lanczos method described here was
first derived in [177] as a special case of the general
nonsymmetric band Lanczos method proposed in [166].
The version of the band Lanczos method stated as
Algorithm 4.12
performs all multiplications with as matrix-vector products
with single vectors.
However, at any stage of the algorithm, it is also possible to
precompute the next
matrix-vector products, which will
be needed in the next
iterations, as a single matrix-matrix
product
with a block
of
vectors.
The procedure is as follows.
Instead of performing step (7) in Algorithm 4.12, we
compute the matrix-matrix product
For Hermitian positive definite matrices ,
yet another variant of Algorithm 4.12, based on coupled
recurrences, was proposed in [35].
The motivation for this variant was the observation that for
ill-conditioned
Hermitian positive definite matrices
, the smallest eigenvalue
obtained from the Lanczos matrix
may become negative;
see [34,35] for examples.
In exact arithmetic, this would be impossible, since the positive
definiteness of
implies that
is also
positive definite.
However, in finite precision arithmetic, roundoff may cause the
matrix
generated by Algorithm 4.12 to be
slightly indefinite.
This can be avoided easily by using coupled recurrences to generate
a Cholesky factor of
, instead of
itself.
More precisely, the recurrences summarized in (4.32)
are replaced by coupled recurrences of the form
Finally, we note that the block Lanczos method
is the more traditional way of extending the
standard Lanczos algorithm for a single starting vector to
multiple starting vectors.
When the block Lanczos method is combined with deflation (as
described, e.g., in [89]), then the resulting algorithm is
mathematically equivalent to the band Lanczos method described
here.
However, the band Lanczos method has two distinct advantages
over the block Lanczos method.
First, deflation is extremely simple, since it requires
only to check the norm of a single vector.
In contrast, in the block Lanczos method, one needs to check if
a whole block of vectors has full rank, and if not, find
the linearly dependent columns.
Typically, this requires the computation of a QR factorization
of each block.
Second, the band Lanczos method actually performs slightly fewer
explicit orthogonalizations, resulting in a Lanczos
matrix
that is slightly sparser than the one
produced by the block Lanczos method.