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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
0
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
- J. Demmel, Applied Numerical Linear Algebra
- B. Parlett, The Symmetric Eigenvalue Problem
