A Centre of Excellence in HPC

Arnoldi’s method is an algorithm that was originally used to reduce an arbitrary matrix \(A \in \mathbb{C}^{n \times n}\) to Hessenberg form. However, it can also be used to approximate eigenvalues as shown in the following.

The following pseudocode illustrates Arnoldi’s method:

```
choose initial vector v(1) with ||v(1)|| = 1
for j = 1,...,m
w = A*v(j)
for i = 1,...,j
h(i,j) = <w, v(i)>
w = w - h(i,j)*v(i)
h(j+1,j) = ||w||_2
v(j+1) = w / h(j+1,j)
```

The procedure starts with an arbitrary normalized vector \(\mathbf{v}_1\).
Then it iteratively computes a *Krylov subspace* \(\mathcal{K} = <\mathbf{v}_1,
A \mathbf{v}_1, A^2 \mathbf{v}_1, ..., A^{m-1} \mathbf{v}_1>\). The whole
system of Krylov vectors is orthogonalized using Gram-Schmidt
orthogonalization.

Projecting the matrix $`A`

$ onto this Krylov subspace then yields

where \(V_m\) is the matrix containing the \(m\) Krylov vectors computed by the
Arnoldi method and \(H_m\) is an upper Hessenberg matrix of dimension \(m\).
Since the dimension of the Hessenberg matrix is usually much smaller than that
of the original matrix \(A\) the eigenvalues of \(H_m\) can efficiently
computed by the QR method. The obtained eigenvalues are called *Ritz
eigenvalues* and they converge to the \(m\) largest eigenvalues of \(A\).