     Next: The Need for Deflation Up: Hermitian Eigenvalue Problems Previous: Software Availability   Contents   Index

# Band Lanczos Method R. Freund

The standard Hermitian Lanczos algorithm uses the Krylov subspaces induced by the matrix and a single starting vector to produce approximate solutions of the Hermitian eigenproblem . However, there are situations where the use of a block of starting vectors, instead of a single starting vector, is preferable. One such case is that of matrices with multiple or closely clustered eigenvalues. To obtain basis vectors for the eigenspace corresponding to such a cluster of eigenvalues, block Krylov subspaces induced by and a block of starting vectors need to be used.

An important application, where multiple starting vectors are given as part of the problem, is reduced-order modeling of -input -output linear dynamical systems; see §7.10.4 below. While this application, in general, involves a non-Hermitian square matrix , a rectangular input'' matrix with columns, and a rectangular output'' matrix with columns, the special case where is Hermitian and the input and output matrices and are identical is of particular importance. For example, this special case arises in the context of interconnect modeling of VLSI circuits; see, e.g., . For this special case, an extension of the Hermitian Lanczos algorithm to multiple starting vectors, namely, the columns of , is needed.

Finally, employing block Krylov subspaces is also beneficial whenever computing matrix-matrix products , where is a matrix with columns, is cheaper than sequentially computing matrix-vector products for vectors. Lanczos methods based on block Krylov subspaces allow computation of all necessary multiplications with as matrix-matrix products with blocks of size , whereas in the standard Hermitian Lanczos algorithm multiplications with have to be computed as a sequence of matrix-vector products .

In this section, we describe a band Lanczos method for the Hermitian eigenvalue problem, (34)

that is based on block Krylov subspaces induced by the matrix and a block of starting vectors, (35)

The matrix and the starting vectors (4.26) induce the block Krylov sequence (36)

The goal of the band Lanczos algorithm is to construct orthonormal vectors, (37)

that build a basis for the subspace spanned by the first linearly independent vectors of the block Krylov sequence (4.27).

Subsections     Next: The Need for Deflation Up: Hermitian Eigenvalue Problems Previous: Software Availability   Contents   Index
Susan Blackford 2000-11-20