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 . A somewhat different version, which also includes a look-ahead procedure to remedy possible breakdowns, is described in .
The version of the band Lanczos method stated as
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