The Arnoldi Iteration

A Krylov method that reduces a large nonsymmetric matrix to a small upper-Hessenberg form, giving eigenvalues and underpinning GMRES.

The nonsymmetric generalization of Lanczos

When a matrix A is not symmetric, its projection onto a Krylov basis is not tridiagonal, and no short recurrence produces an orthonormal basis. The Arnoldi iteration instead uses a full modified Gram-Schmidt orthogonalization at each step, building an orthonormal basis whose projection of A is upper Hessenberg (upper triangular plus one subdiagonal).

The algorithm

At step j, Arnoldi forms A times the latest basis vector, orthogonalizes it against all previous basis vectors (storing the coefficients in the Hessenberg matrix H), and normalizes to get the next vector. Because it orthogonalizes against all prior vectors, both work per step and storage grow with the iteration count, unlike the constant cost of Lanczos.

import numpy as np

def arnoldi(A, v0, m):
    n = len(v0)
    Q = np.zeros((n, m+1))
    H = np.zeros((m+1, m))
    Q[:, 0] = v0 / np.linalg.norm(v0)
    for j in range(m):
        w = A @ Q[:, j]
        for i in range(j+1):
            H[i, j] = Q[:, i] @ w
            w = w - H[i, j] * Q[:, i]
        H[j+1, j] = np.linalg.norm(w)
        if H[j+1, j] < 1e-14:
            return Q[:, :j+1], H[:j+1, :j+1]
        Q[:, j+1] = w / H[j+1, j]
    return Q, H

Two uses

• Eigenvalues: the eigenvalues of the small Hessenberg matrix (Ritz values) approximate those of A, converging first at the periphery of the spectrum
• Linear systems: GMRES minimizes the residual over the Arnoldi subspace to solve Ax = b

Restarting

Because storage grows, Arnoldi is restarted in practice. Implicitly restarted Arnoldi (the basis of ARPACK) applies polynomial filters to compress the subspace toward the eigenvalues of interest while keeping the basis small, making it the standard tool for finding a few eigenvalues of very large nonsymmetric matrices, such as those from linearized plasma stability operators.