Variants

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

This gives us the vector , which is used in the remaining steps of iteration , as well as the vectors

In the following iterations, we will need the vectors

Here, is defined as minus the number of deflations of vectors that will have occurred during these following iterations. Using the procedure outlined in §4.6.4, one can easily obtain the vectors (7.87) as suitable linear combinations of the precomputed vectors (7.86). Similarly, at any stage of the algorithm, it is 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 (11) in Algorithm 7.16, one computes the matrix-matrix product

and then proceeds analogously as for the vectors (7.86).