How to use Lanczos method to compute eigenvalues and eigenvectors

Question

I have a sparse and symmetric matrix A(n x n). The method Lanczos tranforms matrix A into tridiagonal and symmetric matrix T and the Lanczos vectors in matrix V. From there how do I compute k smallest or largest eigenvalues and corresponding eigenvectors?

Answer 1

• For eigenvalues, simply take $k$ largest or smallest eigenvalues of $T$. They are good approximations of $A$, provided that the number of Lanczos iterations is large compared to $k$.

• Things are a little trickier if we want eigenvectors as well.
  The simplest way is to multiply each eigenvector $\mathbf{u}_i$ of $T$ by $V$ to the left, where $V$ is, as you said, the collection of Lanczos vectors. But this approach falls short for many classes of matrices, as round-off errors cause the Lanczos vectors to lose their orthogonality (1).
  
  A better way is to re-orthogonalize the Lanczos vectors in $V$ by doing a Gram-Schmidt step.
  Let $\mathbf{z}$ be the $i$-th Lanczos vector being computed, and let $\mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_{i-1}$ be the previous Lanczos vectors. We mutate $\mathbf{z}$ so as to eliminate all the components of $\mathbf{z}$ that are parallel to any of $\mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_{i-1}$: $$ \mathbf{z}' = \mathbf{z} - \sum_{j=1}^{i-1}(\mathbf{z}^{T}\mathbf{q}_j)\mathbf{q}_j $$ It turns out that we need to re-orthogonalize twice to guarantee the numerical orthogonality of the Lanczos vectors (2).

Reference

1. J. Demmel, Applied Numerical Linear Algebra
2. B. Parlett, The Symmetric Eigenvalue Problem