Next: Variants Up: Band Lanczos Method   Previous: Basic Properties   Contents   Index

## Algorithm

A complete statement of the band Lanczos algorithm for Hermitian matrices is as follows.

Next, we discuss some of the steps of Algorithm 4.12 in more detail.

(4)
Generally, the decision on whether needs to be deflated should be based on checking whether
 (51)

where is a suitably chosen deflation tolerance. The vector is then deflated if (4.42) is satisfied. In this case, the value , if positive, is added to the index set , which contains the indices of the nonzero rows in the part of , and the current block size is updated to . If , the block Krylov sequence (4.27) is exhausted, and the algorithm terminates naturally. If , the vector is deleted, the index of each of the remaining candidate vectors is reset to , and finally, the algorithm returns to step (3). If (4.42) is not satisfied, no deflation is necessary and the algorithm proceeds with step (5).

Usually, in (4.42), one will choose a small tolerance , such as the square root of machine precision. However, does not have to be small; Algorithm 4.12 and its properties remain correct for any choice of . Note that the algorithm performs only exact deflation if one sets in (4.42).

(5)
The vector has passed the deflation check and is now normalized to become the next Lanczos vector . The normalization is such that

(6)
The remaining candidate vectors, , are explicitly orthogonalized against the latest Lanczos vector . Note that in the first steps some will have nonpositive column index. They serve to make the starting basis orthonormal, but need not be stored in the matrix.

(7)
The block Krylov sequence is advanced by computing a new candidate vector, , as the -multiple of the latest Lanczos vector .

(8)
The vector is orthogonalized against the previous Lanczos vectors , , , , where . Here, we exploit the fact that the matrix is Hermitian, and instead of explicitly computing , we set . Note that the 's were computed explicitly in step (6).

(9)
The vector is explicitly orthogonalized against the Lanczos vectors , , and against . Note that modified Gram-Schmidt is used to do this orthogonalization.

(11)
All the nonzero elements in the th row and the th column have now been computed, and they are added to the matrix of the previous iteration , to yield the current matrix . Here, we use the convention that entries and that are not explicitly defined in Algorithm 4.12 are set to zero.

(12)
To test for convergence, the eigenvalues , , of the Hermitian matrix are computed, and the algorithm is stopped if some of the 's are good enough approximations to the desired eigenvalues of .

Next: Variants Up: Band Lanczos Method   Previous: Basic Properties   Contents   Index
Susan Blackford 2000-11-20