NLA MT25, Lanczos iteration
Flashcards
@State (and @visualise) the Lanczos decomposition for symmetric $A \in \mathbb R^{n \times n}$. What three-term recurrence does this imply for the vectors $q _ {k}$?
\[AQ _ k = Q _ k T _ k + q _ {k+1} [0, \ldots, 0, t _ {k+1, k}]\]
where $T _ k$ is symmetric tridiagonal.
@Prove that the Arnoldi decomposition for $A \in \mathbb R^{m \times n}$ simplifies to
\[AQ _ k = Q _ k T _ k + q _ {k+1} [0, \ldots, 0, t _ {k+1, k}]\]
where $T _ k$ is symmetric tridiagonal when $A$ is symmetric.
Note that in the Arnoldi decomposition, we have
\[H _ k = Q _ k^\top A Q _ k\]Hence (@todo).
How much faster is the Lanczos iteration compared to the Arnoldi decomposition?
- Lanczos: $O(nk)$ operations
- Arnoldi: $O(nk^2)$ operations