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
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.