Next: An Adaptively Blocked Lanczos Up: Block Lanczos Methods   Previous: Block Lanczos Methods     Contents   Index

## Basic Algorithm

Given an by matrix and initial by block vectors and such that , the block Lanczos method generates sequences of right and left Lanczos block vectors and . These vectors are the biorthonormal bases of the Krylov subspaces and . Specifically, after steps, the Lanczos procedure determines a block-tridiagonal matrix

and matrices of right and left Lanczos vectors

that satisfy the biorthonormality condition
 (155)

The block Lanczos method uses three-term recurrences
 (156) (157)

for , where . In matrix notation, these quantities satisfy the governing relations
 (158) (159)

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:

 (160) (161)

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

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.

Next: An Adaptively Blocked Lanczos Up: Block Lanczos Methods   Previous: Block Lanczos Methods     Contents   Index
Susan Blackford 2000-11-20