Next: An Adaptively Blocked Lanczos
Up: Block Lanczos Methods
Previous: Block Lanczos Methods
  Contents
  Index
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
![\begin{displaymath}
P^{\ast}_{[j]} Q_{[j]} = I.
\end{displaymath}](img2263.png) |
(155) |
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.
Next: An Adaptively Blocked Lanczos
Up: Block Lanczos Methods
Previous: Block Lanczos Methods
  Contents
  Index
Susan Blackford
2000-11-20