Next: Lanczos Method for Complex Up: Band Lanczos Method   Previous: Application to Reduced-Order Modeling   Contents   Index

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
 (192)

In the following iterations, we will need the vectors
 (193)

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).

Next: Lanczos Method for Complex Up: Band Lanczos Method   Previous: Application to Reduced-Order Modeling   Contents   Index
Susan Blackford 2000-11-20