Band Lanczos Method
  R. Freund

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

$$Ax = \lambda x.$$ (164)

Here, $A$ 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 $AV$ and $A^T W$, where $V$ and $W$ are blocks of vectors, is cheaper than sequentially computing matrix-vector products $Av$ and $A^T w$ for all the columns of $V$ and $W$. 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 $m$ right and $p$ left starting vectors,

$$b_1,b_2,\ldots,b_m\quad \mbox{and}\quad c_1,c_2,\ldots,c_p.$$ (165)

The matrix $A$ 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 $A$ and $A^T$, rather than $A$ and $A^{H}$, 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 $A$ and the starting vectors (7.59) induce the right block Krylov sequence

$$b_1,b_2,\ldots,b_m,A b_1, A b_2, \ldots, A b_m,\ldots, A^{k-1} b_1, \ldots, A^{k-1} b_m, \ldots,$$ (166)

and the left block Krylov sequence

$$c_1,c_2,\ldots,c_p,A^T c_1, A^T c_2, \ldots, A^T c_p,\ldots, (A^T)^{k-1} c_1, \ldots, (A^T)^{k-1} c_p, \ldots.$$ (167)

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

$$v_1,v_2,\ldots,v_j \quad \mbox{and}\quad w_1,w_2,\ldots,w_j,$$ (168)

that build bases for the subspaces spanned by the first $j$ 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., $m=p$, 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 $m,\, p\geq 1$. Even for the special case $m=p$, there are advantages of the band method over the block Lanczos method; see §7.10.5 below.