The traditional approach to extending Krylov subspace
techniques for single starting vectors to multiple starting
vectors is to design a block version of the Krylov subspace
algorithm.
A block version of the non-Hermitian Lanczos process was first
proposed in [260,261].
However, this block Lanczos algorithm assumes that the
right and left starting blocks have the same size, i.e., ,
and it does not have deflation or look-ahead.
It is easy to see that any block version of the
non-Hermitian Lanczos process requires all right and left
blocks to have the same size.
In particular, any block version is
restricted to the special case when
and when possible deflations
occur simultaneously in the right and left block Krylov
sequences, so that
throughout the algorithm.
The non-Hermitian band Lanczos algorithm described in this
section, however, suffers from none of these restrictions.
In particular, it can be used for starting blocks of arbitrary
sizes , and it allows deflations that occur
independently in the right and left block Krylov
sequences.
The version of the band Lanczos method stated in Algorithm 7.16 first appeared in this form in [175]. A somewhat different version, which also includes a look-ahead procedure to remedy possible breakdowns, is described in [5].
The version of the band Lanczos method stated as
Algorithm 7.16
performs all multiplications with and
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 with
, which will
be needed in the next
iterations, as a single matrix-matrix
product
with a block
of
vectors.
Indeed, instead of performing step (9) in Algorithm 7.16,
one computes the matrix-matrix product