Notes - NLA MT25, Arnoldi iteration

What is the purpose of the Arnoldi iteration?

Given a matrix $A \in \mathbb R^{n \times n}$ and initial vector $v$, find an orthonormal basis $[q _ 1, \ldots, q _ r]$ of its Krylov subspace $\mathcal K _ r (A, v) = \text{span}(v, Av, \ldots, A^{r-1} v)$.

Suppose we have a matrix $A \in \mathbb R^{n \times n}$ and an initial vector $v$. The Arnoldi iteration finds an orthonormal basis $[q _ 1, \ldots, q _ r]$ of its Krylov subspace $\mathcal K _ r(A, v)$. @State the full outputs of this algorithm.

$Q _ r = [q _ 1 \mid \cdots \mid q _ r]$ s.t. $\text{span}(q _ 1, \ldots, q _ r) = \mathcal K _ r(A, v)$
$H _ r$ upper Hessenberg
$H _ r = Q _ r^\top A Q _ r$

@State (and @visualise) the Arnoldi decomposition for $A \in \mathbb R^{n \times n}$ and a vector $b \in \mathbb R$.

\[AQ _ k = Q _ k H _ k + q _ {k+1} [0, \ldots, 0, h _ {k+1, k}]\]

with $Q _ k = [q _ 1, \ldots, q _ k]$, $Q _ {k+1} = [Q _ k, q _ {k+1}]$ and $\text{span}(Q _ k) = \text{span}([b, Ab, \ldots, A^{k+1} b])$.

Suppose:

$A \in \mathbb R^{n \times n}$
$b \in \mathbb R^n$

Describe the Arnlodi iteration for computing an orthonormal basis $[q _ 1, \ldots, q _ {r}]$ of its Krylov subspace and the other useful outputs of this algorithm.

Let $q _ 1 = b / \vert \vert b \vert \vert _ 2$
For $k = 1, 2, \ldots, r-1$:
- Set $v = Aq _ k$
- For $j = 1, 2, \ldots, k$
  - $h _ {jk} = q _ j^\top v$
  - $v = v - h _ {jk} q _ j$
- $h _ {k+1, k} = \vert \vert v \vert \vert _ 2$
- $q _ {k+1} = v/h _ {k+1, k}$

Then the outputs are

$Q _ r = [q _ 1 \mid \cdots \mid q _ r]$ s.t. $\text{span}(q _ 1, \ldots, q _ r) = \mathcal K _ r(A, v)$
$H _ r$ upper Hessenberg
$H _ r = Q _ r^\top A Q _ r$

@algorithm~

Suppose:

$A \in \mathbb R^{n \times n}$
$b \in \mathbb R^n$

The Arnlodi iteration for computing an orthonormal basis $[q _ 1, \ldots, q _ {r}]$ of its Krylov subspace is given by:

Let $q _ 1 = b / \vert \vert b \vert \vert _ 2$
For $k = 1, 2, \ldots, r-1$:
- Set $v = Aq _ k$
- For $j = 1, 2, \ldots, k$
  - $h _ {jk} = q _ j^\top v$
  - $v = v - h _ {jk} q _ j$
- $h _ {k+1, k} = \vert \vert v \vert \vert _ 2$
- $q _ {k+1} = v/h _ {k+1, k}$

and outputs

$Q _ r = [q _ 1 \mid \cdots \mid q _ r]$ s.t. $\text{span}(q _ 1, \ldots, q _ r) = \mathcal K _ r(A, v)$
$H _ r$ upper Hessenberg
$H _ r = Q _ r^\top A Q _ r$

Suppose that $h _ {k+1, k} \ne 0$ for $k = 1, \ldots, \ell$. @Prove that then for $k = 1, \ldots, \ell$, we have

\[\text{span}(q _ 1, \ldots, q _ k) = \mathcal K _ k(A, b)\]

Induct on $\ell$.

Base case $\ell = 1$: Then $q _ 1 = q _ \ell = p _ {\ell-1}(A)b$ where $p _ {\ell-1}$ is a polynomial of degree $\ell - 1 = 0$, so it is a constant.

Inductive step: Suppose that the result holds for $k = 1, \ldots, \ell$. Then for $\ell + 1$, we obtain

\[q _ {\ell + 1} = \frac{1}{h _ {\ell + 1, \ell}}(Aq _ \ell - \sum^\ell _ {j=1} h _ {j, \ell} q _ j)\]

which has exact degree $\ell$, and hence lies in the order-$\ell+1$ Krylov subspace.

Suppose:

$A \in \mathbb R^{n \times n}$
$b \in \mathbb R^n$

The Arnlodi iteration for computing an orthonormal basis $[q _ 1, \ldots, q _ {r}]$ of its Krylov subspace is given by:

Let $q _ 1 = b / \vert \vert b \vert \vert _ 2$
For $k = 1, 2, \ldots, r-1$:
- Set $v = Aq _ k$
- For $j = 1, 2, \ldots, k$
  - $h _ {jk} = q _ j^\top v$
  - $v = v - h _ {jk} q _ j$
- $h _ {k+1, k} = \vert \vert v \vert \vert _ 2$
- $q _ {k+1} = v/h _ {k+1, k}$

and outputs

$Q _ r = [q _ 1 \mid \cdots \mid q _ r]$ s.t. $\text{span}(q _ 1, \ldots, q _ r) = \mathcal K _ r(A, v)$
$H _ r$ upper Hessenberg
$H _ r = Q _ r^\top A Q _ r$

What is meant by a “happy breakdown” in this algorithm?

At some step, $h _ {k+1, k} \ne 0$. If this happens, then it actually implies that the solution can be found easily.

What is the cost of the Arnoldi iteration for finding an orthogonal basis for $\mathcal K _ k({A, b})$?

\[O(nk^2)\]

NLA MT25, Arnoldi iteration

Flashcards

Related posts