Co-design at POP CoE project

Arnoldi's method

Arnoldi’s method is an algorithm that was originally used to reduce an arbitrary matrix 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 . Then it iteratively computes a Krylov subspace . The whole system of Krylov vectors is orthogonalized using Gram-Schmidt orthogonalization.

Projecting the matrix $A$ onto this Krylov subspace then yields

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

Related programs: Related disciplines: Eigenvalue problems ·