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
![\begin{displaymath}
\Vert\hat{v}_j\Vert _2 \leq {\tt dtol},
\end{displaymath}](img1188.png) |
(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