and matrices of right and left Lanczos vectors

that satisfy the biorthonormality condition

The block Lanczos method uses three-term recurrences

for , where . In matrix notation, these quantities satisfy the governing relations

where is a by matrix of which the bottom square is an identity matrix and zeros elsewhere.

To use the Lanczos method
for approximating eigenvalues and eigenvectors of , we solve
the eigenvalue problem of the block-tridiagonal matrix .
Each eigentriplet
of ,

determines a Ritz triplet , where and . In general, Ritz triplets approximate outer eigentriplets of first.

To assess the approximation,
let and denote the corresponding right and left
residual vectors:

Substitute (7.52) and (7.53), respectively, and there appears

A Ritz value is considered to have converged if both residual norms are sufficiently small. Similarly, the residuals can also be used to determine a backward error bound for the triplet, as in the case for the standard non-Hermitian Lanczos algorithm (see §7.8).

A simple blocked version of the basic non-Hermitian Lanczos method is presented in Algorithm 7.14.

We now comment on some steps of Algorithm 7.14.

**(1)**- The starting vectors and are best selected by the
user to embody any available knowledge concerning 's wanted
eigenvectors. In the absence of such knowledge, choose
to be a real orthonormalized random matrix
and let .
The block size should be chosen to be larger than or equal to the multiplicity of any wanted eigenvalue. If the multiplicities are unknown, typical values of are , , and .

**(2), (3), (20), (21)**- The user is required to furnish subroutines to calculate the
products and for an arbitrary matrix .
This gives the user a chance to calculate these products with only
one pass over the data structure defining and ,
with possible improvements in efficiency.
**(8), (9), (10)**- First, the QR factorizations of and are computed.
If and are both of full rank, then
and are by matrices such that
, and both
and are by right upper triangular matrices.
If either or is not of full rank, then an invariant subspace has
been revealed. Continuing the recurrence in the rank-deficient
case is discussed in §7.9.2.
**(12)**- If is singular or nearly singular,
that is, if there is a zero or a very tiny singular value, then
there is a
*breakdown*. Proper action must be taken to continue. See §7.9.2 for possible treatments. **(17), (18)**- The eigentriplets of can be computed
using the method discussed in §7.3.
The convergence of Ritz values can be tested by the norms of
residuals (7.56) and (7.57).
For more details on accessing the accuracy of the approximation,
see § 7.8.2 and §7.13
and [29].
When becomes large, solving the eigenproblem of becomes time consuming. A simple way to reduce the cost is to do this periodically, say every five steps.

**(19)**- As in the unblocked Lanczos method, in the presence of finite precision
arithmetic, the biorthogonality of the block Lanczos vectors
and deteriorates. The TSMGS
process can be used to biorthogonalize and in place
against the previous Lanczos vectors
and
.
`PROCEDURE TSMGS`**for**

**end** **(25)**- This is recommended only if the biorthogonality of the Lanczos vectors is well maintained. The approximate eigenvectors and corresponding to converged Ritz values are computed and the residuals (7.54) and (7.55) are checked again relative to and . Note that the norms can be greater than the estimates computed at step (17). This is a side-effect of the ill-conditioning of the Lanczos basis vectors.