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

##

The Need for Deflation

The use of multiple starting vectors causes an additional
difficulty that does not arise in the single-vector case .
The standard Lanczos algorithm for a single starting vector
terminates after iterations if the next Krylov vector, , is
linearly dependent on the previous Krylov vectors, i.e.,
.
In this case, the Lanczos vectors build a basis of the
-invariant subspace
and all eigenvalues of
the Lanczos tridiagonal matrix are also eigenvalues of .
The subspace
being -invariant means that
the Krylov sequence has been fully exhausted, and so adding further
Krylov vectors would not expand the Krylov subspace.
This termination after iterations is thus natural.

In the case , however, the occurrence of a first linearly
dependent vector in (4.27) does not mean
that the block Krylov sequence is exhausted.
It simply means that the linearly dependent vector and all its
following -multiples do not contain any new information,
and therefore, these vectors should be removed from (4.27).
This process of detecting and deleting linearly dependent vectors
is called *exact deflation*.
For example, suppose the starting vectors (4.26)
are such that the vector is a linear combination
of
.
Then is certainly linearly dependent on the Krylov vectors to
the left of in (4.27);
in fact, each vector with is linearly dependent
on vectors to the left of in (4.27).
In this case, all vectors , , need to be deleted
from (4.27), resulting in the deflated
block Krylov sequence

For , in contrast to the case ,
the first occurrence of an exact deflation does not imply that
any of the eigenvalues of the Lanczos matrix produced by the
band Lanczos method is also an eigenvalue of .
However, after exact deflations have occurred, then, just as
in the case , the Lanczos vectors span an -invariant
subspace and all the eigenvalues of the Lanczos matrix
are also eigenvalues of .
Of course, in finite precision arithmetic, it is impossible to
distinguish between exactly linearly dependent and
almost linearly dependent vectors.
Therefore, in practice, almost linearly dependent vectors also
have to be detected and deleted.
In what follows, we will refer to the process of detecting and
deleting linearly dependent and almost linearly dependent vectors
as *deflation*.

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