The Need for Deflation

The use of $p>1$ multiple starting vectors causes an additional difficulty that does not arise in the single-vector case $p=1$. The standard Lanczos algorithm for a single starting vector $b$ terminates after $j$ iterations if the next Krylov vector, $A^j b$, is linearly dependent on the previous Krylov vectors, i.e., $A^j b \in {\cal K}^j(A,b)$. In this case, the Lanczos vectors build a basis of the $A$-invariant subspace ${\cal K}^j(A,b)$ and all eigenvalues of the Lanczos tridiagonal matrix are also eigenvalues of $A$. The subspace ${\cal K}^j(A,b)$ being $A$-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 $j$ iterations is thus natural.

In the case $p>1$, 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 $A$-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 $A b_1$ is a linear combination of $b_1,b_2,\ldots,b_p$. Then $A b_1$ is certainly linearly dependent on the Krylov vectors to the left of $A b_1$ in (4.27); in fact, each vector $A^i b_1$ with $i\geq 1$ is linearly dependent on vectors to the left of $A^i b_1$ in (4.27). In this case, all vectors $A^i b_1$, $i\geq 1$, need to be deleted from (4.27), resulting in the deflated block Krylov sequence

$$b_1,b_2,\ldots,b_p,A b_2, A b_3, \ldots, A b_{p},\ldots, A^{k-1} b_2, A^{k-1} b_3, \ldots, A^{k-1} b_{p}, \ldots.$$

For $p>1$, in contrast to the case $p=1$, 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 $A$. However, after $p$ exact deflations have occurred, then, just as in the case $p=1$, the Lanczos vectors span an $A$-invariant subspace and all the eigenvalues of the Lanczos matrix are also eigenvalues of $A$.

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.