arnoldi

Arnoldi is an algorithm in numerical linear algebra for computing eigenvalues and eigenvectors of a general square matrix. It builds an orthonormal basis of the Krylov subspace K_m(A, v1) = span{v1, Av1, A^2 v1, ..., A^{m-1} v1} and reduces A to upper Hessenberg form. The process yields an orthonormal matrix Q_m = [q1, ..., qm] and an upper Hessenberg matrix H_m such that A Q_m ≈ Q_m H_m, with a small residual term A Q_m − Q_m H_m = h_{m+1,m} q_{m+1} e_m^T.

In the Arnoldi iteration, one starts with a nonzero vector v1 and normalizes it to obtain q1. For j = 1 to m, compute w = A q_j; project w onto the existing basis to obtain h_{i,j} = q_i^T w for i = 1,...,j, and orthogonalize w against all q_i. Set h_{j+1,j} = ||w|| and, if nonzero, form q_{j+1} = w / h_{j+1,j}. The resulting H_m is upper Hessenberg. The eigenvalues of H_m (the Ritz values) approximate the eigenvalues of A, and the corresponding Ritz vectors give approximations to eigenvectors of A in the Q_m basis.

If A is symmetric, the Hessenberg matrix becomes tridiagonal and the method reduces to the Lanczos algorithm. Arnoldi is central to many large-scale eigenvalue solvers and is often used with implicit restarting (Implicitly Restarted Arnoldi) in software such as ARPACK. The method is particularly effective for sparse or structured matrices and for computing a few eigenvalues of large systems.