Deflation

As in the case of the Hermitian band Lanczos method, the use of multiple starting vectors necessitates a suitable deflation procedure to delete linearly and almost linearly dependent vectors in the block Krylov sequences. We refer to §4.6.1 for a discussion of deflation in the Hermitian case.

In the non-Hermitian case, deflation in general occurs independently in the right and left block Krylov sequences. An exact deflation in the right block Krylov sequence (7.60) means that a vector, say $A^i b_j$, in the sequence (7.60) is linearly dependent on vectors to the left of $A^i b_j$ in (7.60) and that this vector and all its $A$-multiples are removed from (7.60). Similarly, an exact deflation in the left block Krylov sequence (7.61) means that a vector in the sequence (7.61) is linearly dependent on previous Krylov vectors in (7.61) and that this vector and all its $A^T$-multiples are removed from (7.61). After $m$ exact deflations in the right block Krylov sequence (7.60) have occurred, the remaining nondeflated vectors of (7.60) span an $A$-invariant subspace. Furthermore, the right Lanczos vectors in (7.62) build a suitable basis for this $A$-invariant subspace, and all the eigenvalues of the Lanczos matrix $T_j^{\rm (pr)}$ defined in §7.10.2 below are also eigenvalues of $A$. Similarly, after $p$ exact deflations in the left block Krylov sequence (7.61) have occurred, the remaining nondeflated vectors of (7.61) span an $A^T$-invariant subspace. The left Lanczos vectors in (7.62) build a suitable basis for this $A^T$-invariant subspace and all the eigenvalues of the Lanczos matrix $T_j^{\rm (pr)}$ 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 the sequel, we will refer to the process of detecting and deleting linearly dependent and almost linearly dependent vectors as deflation.