NLA MT25, Lanczos decomposition and iteration

The Lanczos decomposition is the Arnoldi decomposition for symmetric $A$.

When $A = A^\top$, the Arnoldi decomposition simplifies. The Lanczos decomposition produces $Q _ k = [q _ 1 \mid \cdots \mid q _ k] \in \mathbb R^{n \times k}$ with orthonormal columns spanning $\mathcal K _ k(A, b)$ and a tridiagonal matrix $T _ k \in \mathbb R^{k \times k}$, satisfying:

or equivalently with $Q _ {k+1} = [Q _ k \mid q _ {k+1}]$ and $\tilde T _ k \in \mathbb R^{(k+1) \times k}$:

where $T _ k$ is symmetric tridiagonal

Schematically,

Three-term recurrence. Reading off the $k$th column of $AQ _ k = Q _ {k+1}\tilde T _ k$ — whose only nonzero entries are $t _ {k-1,k}, t _ {k,k}, t _ {k+1,k}$ —

with $t _ {k-1,k} = t _ {k,k-1}$ by symmetry of $T _ k$. Writing $\alpha _ k = t _ {k,k} = q _ k^\top A q _ k$ for the diagonal and $\beta _ k = t _ {k+1,k} = t _ {k,k+1}$ for the off-diagonal, this rearranges into the Lanczos iteration

i.e. each new basis vector comes from only the previous two. That is the payoff of symmetry: Lanczos needs $O(1)$ stored vectors and $O(n)$ work per step (one matvec + two axpys, $\alpha _ k$ from an inner product, $\beta _ k$ from a norm), versus Arnoldi’s full Gram–Schmidt against all previous $q _ j$ ($O(nk)$ work and storage at step $k$).

Algorithm:

• Set $q _ 1 = b / \|b\| _ 2$.
• For $k = 1, 2, \ldots, r-1$:
  • Set $v = Aq _ k$ (apply $A$ to the latest basis vector)
  • $t _ {k, k} = q _ k^\top v$ (the new $q _ k$-component of $Aq _ k$)
  • $v = v - t _ {k, k} q _ k - t _ {k-1, k} q _ {k-1}$ (when $k = 1$, omit the last term. Here we orthogonalise against only the last two basis vectors, since orthogonality against the others is guaranteed, ∆lanczos-three-term-recurrence).
  • $t _ {k+1, k} = \|v\| _ 2$ (off-diagonal entry, equals $t _ {k, k+1}$ by symmetry of $T _ r$)
  • If $t _ {k+1, k} = 0$, this is a ∆happy-breakdown and the Krylov subspace is $A$-invariant, and we should stop. Otherwise,
  • $q _ {k+1} = v/t _ {k+1, k}$.

Outputs, after $r$ steps:

• $Q _ r = [q _ 1 \mid \cdots \mid q _ r] \in \mathbb R^{n \times r}$, orthonormal columns spanning $\mathcal K _ r(A, b) = \text{span}(b, Ab, \ldots, A^{r-1} b)$.
• $T _ r \in \mathbb R^{r \times r}$ symmetric tridiagonal. Its diagonal entries are $t _ {k,k}$ and off-diagonal entries are $t _ {k, k-1} = t _ {k-1, k}$ computed above.

Time:

• $r$ matrix-vector products with $A$: $O(rn^2)$
• $O(r)$ inner products of length $n$ for the orthogonalisation
• Total: $O(nr)$, vs the ∆arnoldi-iteration's $O(nr^2)$.

Memory:

• $O(n)$ to store $q _ {k-1}$ and $q _ k$.
• However, downstream methods based on Lanczos may require all of $Q _ k$, and the iteration is known to suffer from ∆lanczos-loss-of-orthogonality in practice, and so we may need to occasionally re-orthogonalise against the whole $Q _ k$.
• (Compare to ∆arnoldi-iteration, which requires $O(nk)$ to store the full $Q _ k$)

Reading off the $k$th column of $AQ _ k = Q _ k T _ k + t _ {k+1, k} q _ {k+1} e _ k^\top$:

which rearranges to the three-term recurrence

This is helpful because computing $q _ {k+1}$ only requires orthogonalising against $q _ k$ and $q _ {k-1}$, which reduces to $O(n)$ per step rather than $O(nk)$.

Setup: From the Arnoldi iteration applied to $A$ and $b$, the basis matrix $Q _ k = [q _ 1 \mid \cdots \mid q _ k]$ has orthonormal columns, and $H _ k := Q _ k^\top A Q _ k$ is, by construction, upper Hessenberg, since its entries $h _ {j,i} = q _ j^\top A q _ i$ vanish whenever $j > i+1$ because step $i$ of Arnoldi, $Aq _ i$ is orthogonalised against $q _ 1, \ldots, q _ i$ only.

Symmetry forces tridiagonality. Since $A = A^\top$,

so $H _ k$ is symmetric. Since it is both symmetric and upper Hessenberg, it must be tridiagonal.

Setting $T _ k := H _ k$, the Arnoldi decomposition $AQ _ k = Q _ k H _ k + h _ {k+1, k} q _ {k+1} e _ k^\top$ becomes

with $T _ k$ symmetric tridiagonal and $t _ {k+1, k} := h _ {k+1, k}$.

How much faster is the Lanczos iteration compared to the Arnoldi decomposition?::

• Lanczos: $O(nk)$ operations
• Arnoldi: $O(nk^2)$ operations

In exact arithmetic, the basis vectors $q _ i$ produced by Lanczos satisfy $Q _ k^\top Q _ k = I _ k$ exactly. In floating point, the computed $\hat Q _ k$ progressively loses the property, so that $\hat Q _ k^\top \hat Q _ k \ne I _ k$, with the discrepancy growing as $k$ increases. This is because rounding errors in the ∆lanczos-three-term-recurrence introduce small components along the earlier basis vectors.

By reorthogonalisation: re-orthogonalise the new $q _ {k+1}$ against the full $Q _ k$ (rather than just $q _ k, q _ {k-1}$), recovering numerical orthogonality at the cost of $O(nk)$ work and $O(nk)$ memory — losing Lanczos’s main advantage over Arnoldi. Strategies are full (against all of $Q _ k$ at every step), selective (only against vectors tied to converged Ritz values), or partial (against a recent window). Lecture mentions the remedy without specifying which.

$H _ k := Q _ k^\top A Q _ k$ is upper Hessenberg by construction of Arnoldi. When $A = A^\top$, $H _ k^\top = Q _ k^\top A^\top Q _ k = Q _ k^\top A Q _ k = H _ k$, so $H _ k$ is symmetric. A matrix that is both symmetric and upper Hessenberg has zero entries everywhere except the diagonal and first sub/super-diagonals — i.e. it is tridiagonal.