# Arnoldi's method

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

$V_m^* A V_m = H_m,$

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$$.

Related discipline(s): Eigenvalue problems