Next: Deflation Up: Non-Hermitian Eigenvalue Problems Previous: Notes and References   Contents   Index

# Band Lanczos Method R. Freund

The standard non-Hermitian Lanczos algorithm as presented in §7.8 uses the Krylov subspaces induced by the matrix and a pair of single right and left starting vectors and , to produce approximate solutions of the NHEP,

 (164)

Here, is a square, in general non-Hermitian matrix.

There are situations where the use of blocks of right and left starting vectors, instead of a pair of single starting vectors, is preferable. One such case is eigenvalue computations for matrices with multiple or closely clustered eigenvalues. Another important application is reduced-order modeling of linear dynamical systems. Here, the right and left starting blocks are given as part of the problem, as is described in more detail in §7.10.4 below. Finally, the use of blocks of starting vectors is also beneficial whenever computing matrix-matrix products and , where and are blocks of vectors, is cheaper than sequentially computing matrix-vector products and for all the columns of  and . Block Lanczos methods for blocks of equal size were discussed in §7.9.

In this section, we describe the non-Hermitian band Lanczos method, which extends the standard non-Hermitian Lanczos algorithm for single starting vectors to blocks of right and left starting vectors,

 (165)

The matrix and the vectors (7.59) are allowed to be real or complex. However, even when they are complex, we will state the algorithm in terms of and , rather than and , since this way, we can avoid unnecessary complex conjugations in the recurrence relations used in the algorithm. We stress that both formulations are equivalent.

The matrix and the starting vectors (7.59) induce the right block Krylov sequence

 (166)

and the left block Krylov sequence
 (167)

The goal of the band Lanczos algorithm is to construct suitable right and left Lanczos vectors,
 (168)

that build bases for the subspaces spanned by the first linearly independent vectors of the block Krylov sequences (7.60) and (7.61), respectively.

The non-Hermitian band Lanczos method discussed in this section can also be viewed as an extension of the Hermitian band Lanczos method described in §4.6 to general square non-Hermitian matrices. For the special case of right and left starting blocks of the same size, i.e., , the band Lanczos method is also related to the block Lanczos method described in §7.9. However, the band Lanczos method is more general in that it can handle the case of arbitrary block sizes . Even for the special case , there are advantages of the band method over the block Lanczos method; see §7.10.5 below.

Subsections

Next: Deflation Up: Non-Hermitian Eigenvalue Problems Previous: Notes and References   Contents   Index
Susan Blackford 2000-11-20