Band Lanczos Method
  R. Freund

The standard Hermitian Lanczos algorithm uses the Krylov subspaces induced by the matrix $A$ and a single starting vector $b$ to produce approximate solutions of the Hermitian eigenproblem $Ax = \lambda x$. However, there are situations where the use of a block of $p$ 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 $p$ eigenvalues, block Krylov subspaces induced by $A$ and a block of $p$ 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 $m$-input $p$-output linear dynamical systems; see §7.10.4 below. While this application, in general, involves a non-Hermitian square matrix $A$, a rectangular ``input'' matrix $B$ with $m$ columns, and a rectangular ``output'' matrix $C$ with $p$ columns, the special case where $A$ is Hermitian and the input and output matrices $B$ and $C$ are identical is of particular importance. For example, this special case arises in the context of interconnect modeling of VLSI circuits; see, e.g., [176]. For this special case, an extension of the Hermitian Lanczos algorithm to multiple starting vectors, namely, the $p$ columns of $B=C$, is needed.

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

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

$$A x = \lambda x, %%\quad \mbox{where} \quad A = A^H,$$ (34)

that is based on block Krylov subspaces induced by the matrix $A$ and a block of $p$ starting vectors,

$$b_1,b_2,\ldots,b_p.$$ (35)

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

$$b_1,b_2,\ldots,b_p,A b_1, A b_2, \ldots, A b_p,\ldots, A^{k-1} b_1, A^{k-1} b_2, \ldots, A^{k-1} b_p, \ldots.$$ (36)

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

$$v_1,v_2,\ldots,v_j,$$ (37)

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