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., $m=p$, 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 $m=p$ and when possible deflations occur simultaneously in the right and left block Krylov sequences, so that $m_c=p_c$ 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 $m,\, p\geq 1$, 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 $A$ and $A^T$ as matrix-vector products with single vectors. However, at any stage of the algorithm, it is also possible to precompute the next $m_c$ matrix-vector products with $A$, which will be needed in the next $m_c$ iterations, as a single matrix-matrix product $AV$ with a block $V$ of $m_c$ vectors. Indeed, instead of performing step (9) in Algorithm 7.16, one computes the matrix-matrix product

$$A \left[ \begin{array}{ccccc} v_j & \hat{v}_{j+1} & \hat{v}_{j+2} & \cdots & \hat{v}_{j+m_c-1} \end{array} \right].$$

This gives us the vector $\hat{v}_{j+m_c} = A v_j$, which is used in the remaining steps of iteration $j$, as well as the vectors

$$A \hat{v}_{j+1}, A \hat{v}_{j+2}, \ldots, A \hat{v}_{j+m_c-1}.$$ (192)

In the following $m_c-1$ iterations, we will need the vectors

$$A v_{j+1}, A v_{j+2}, \ldots, A v_{j+m_c^{\prime}-1}.$$ (193)

Here, $m_c^{\prime}$ is defined as $m_c$ minus the number of deflations of $\hat{v}_k$ vectors that will have occurred during these following $m_c-1$ 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 $p_c$ matrix-vector products with $A^T$, which will be needed in the next $p_c$ iterations, as a single matrix-matrix product $A^T W$ with a block $W$ of $p_c$ vectors. Indeed, instead of performing step (11) in Algorithm 7.16, one computes the matrix-matrix product

$$A^T \left[ \begin{array}{ccccc} w_j & \hat{w}_{j+1} & \hat{w}_{j+2} & \cdots & \hat{w}_{j+p_c-1} \end{array} \right]$$

and then proceeds analogously as for the vectors (7.86).