8
$\begingroup$

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?

$\endgroup$
11
$\begingroup$
  • 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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.