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

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\).