19 Lanczos Algorithm
Iterative method for finding extreme eigenpairs of large, symmetric matrices without explicit \(O(n^2)\) formation.
(Symmetric assumption) Lanczos applies to symmetric or Hermitian matrices. For nonsymmetric matrices, use Arnoldi or GMRES-type constructions.
19.1 Krylov Subspaces
\(\mathcal{K}_k(\bA, \bv) = \text{span}\{\bv,\, \bA\bv,\, \bA^2\bv,\, ...,\, \bA^{k-1}\bv\}\). \(\bA^j\bv\) amplifies components along dominant eigenvectors, concentrating information about the spectral edges.
(Power iteration with memory) Power iteration keeps only the newest vector. Lanczos keeps an orthonormal basis for the whole Krylov subspace, so it can approximate several eigenvalues at once.
19.2 The Lanczos Recurrence
The process builds an orthonormal basis \(V_k = [\bv_1, ..., \bv_k]\) for \(\mathcal{K}_k\) satisfying: \[ \begin{align} \bA V_k = V_k T_k + \beta_k \bv_{k+1} \be_k^T. \end{align} \]
\(T_k\): Symmetric tridiagonal matrix.
\(\alpha_j = \bv_j^T \bA \bv_j\): Rayleigh quotients (diagonal).
Orthogonalization coefficients (off-diagonal).
In exact arithmetic, \[ \begin{align} T_k=V_k^T\bA V_k. \end{align} \] Thus Lanczos replaces the large symmetric matrix \(\bA\) by a small symmetric tridiagonal projection.
Left multiply the Lanczos relation in the result above by \(V_k^T\): \[ \begin{align} V_k^T\bA V_k = V_k^T V_k T_k+\beta_k V_k^T\bv_{k+1}\be_k^T. \end{align} \] Since the Lanczos vectors are orthonormal, \(V_k^T V_k=\bI\) and \(V_k^T\bv_{k+1}=\bzero\). Hence \(V_k^T\bA V_k=T_k\).
Performance Advantage: Unlike Gram-Schmidt, which orthogonalizes against all previous vectors, Lanczos only requires the two previous vectors (three-term recurrence). This makes it \(O(k \cdot \text{nnz})\) for sparse matrices.
19.3 Ritz Values and Vectors
Approximations to the true eigenpairs from the Krylov subspace.
Ritz Value (\(\theta_i\)): Eigenvalue of \(T_k\).
\(V_k \bs_i\), where \(\bs_i\) is an eigenvector of \(T_k\).
The residual of the \(i\)-th Ritz pair \((\theta_i, \tilde{\bu}_i)\) satisfies: \[ \begin{align} \|\bA\tilde{\bu}_i - \theta_i \tilde{\bu}_i\|_2 = \beta_k |s_i(k)|. \end{align} \] Significance: Convergence of a Ritz pair can be monitored for \(O(k)\) cost without forming the full \(n\)-vector \(\tilde{\bu}_i\).
Starting from the Lanczos relation \(\bA V_k = V_k T_k + \beta_k \bv_{k+1} \be_k^T\), multiply by the \(i\)-th eigenvector \(\bs_i\) of \(T_k\) on the right: \[ \begin{align} \bA V_k \bs_i &= V_k T_k \bs_i + \beta_k \bv_{k+1} \be_k^T \bs_i \\ \bA \tilde{\bu}_i &= V_k (\theta_i \bs_i) + \beta_k \bv_{k+1} s_i(k). \end{align} \] where \(s_i(k)\) is the \(k\)-th entry of \(\bs_i\). Rearranging: \[ \begin{align} \bA \tilde{\bu}_i - \theta_i \tilde{\bu}_i = \beta_k \bv_{k+1} s_i(k). \end{align} \] Taking the \(L_2\) norm and using the fact that \(\|\bv_{k+1}\|_2 = 1\): \[ \begin{align} \|\bA \tilde{\bu}_i - \theta_i \tilde{\bu}_i\|_2 &= |\beta_k s_i(k)| \|\bv_{k+1}\|_2 \\ &= \beta_k |s_i(k)|. \end{align} \]
Ghost Eigenvalues: In floating-point, the three-term recurrence loses orthogonality, leading to ``ghost’’ (spurious) copies of eigenvalues. (Reorthogonalization) Use full or selective reorthogonalization to maintain basis integrity.
Connection to Conjugate Gradient: The Lanczos algorithm applied to a symmetric system \(\bA\bx=\bb\) is mathematically equivalent to the Conjugate Gradient method. Both algorithms build the same Krylov subspace and produce identical iterates in exact arithmetic.
Carry out 2 steps of Lanczos for \(\bA = \text{diag}(5, 3, 1)\) starting with \(\bv_1 = \frac{1}{\sqrt{3}}\mathbf{1}\).
Verify the result above numerically for a random symmetric matrix.
Implement Lanczos on a \(50 \times 50\) Hilbert matrix. Count spurious eigenvalues without reorthogonalization.