the Arnoldi iteration
/ ar-NOHL-dee /
The Lanczos algorithm is wonderful, but it relies entirely on the matrix being symmetric — that is what gives the short three-term recurrence. What if you need a few eigenvalues of a huge sparse matrix that is NOT symmetric (a fluid-dynamics Jacobian, a Markov transition matrix, a stability operator)? The Arnoldi iteration is the answer: it is the natural generalization of Lanczos to general matrices, building an orthonormal basis of the same Krylov subspace and projecting the matrix onto it.
Arnoldi grows the Krylov subspace spanned by q_1, A q_1, A^2 q_1, ... and orthonormalizes the new vector against ALL previous ones using modified Gram-Schmidt. Because the matrix is no longer symmetric, you lose the short recurrence — each new basis vector q_{j+1} must be orthogonalized against every earlier q_i, so step j costs O(j) inner products and the cost and storage grow with the number of steps. The projected matrix is no longer tridiagonal but upper HESSENBERG: a small k-by-k Hessenberg matrix H_k whose eigenvalues (the Ritz values) approximate the extreme eigenvalues of A. You compute those small eigenvalues with the QR algorithm. (In fact, Lanczos is exactly Arnoldi applied to a symmetric matrix, where the Hessenberg matrix collapses to tridiagonal and the long recurrence shortens to three terms.)
Two practical realities. Because the recurrence is long, you cannot run Arnoldi for thousands of steps — memory and orthogonalization cost grow. The fix is RESTARTING: run k steps, keep the most useful directions (the implicitly restarted Arnoldi method, IRAM, implemented in the celebrated ARPACK library and behind MATLAB's eigs and SciPy's eigs), discard the rest, and continue. The other reality is honesty about nonsymmetric matrices themselves: their eigenvalues can be ill-conditioned (Bauer-Fike) and their Ritz values can converge erratically or to the wrong place, so Arnoldi for nonsymmetric problems demands more care and validation than Lanczos for symmetric ones. The same Arnoldi machinery, incidentally, underlies the GMRES method for solving nonsymmetric linear systems.
To find the rightmost eigenvalues (largest real part) of a large nonsymmetric fluid-stability matrix — the ones that signal an instability — you run Arnoldi for, say, 30 steps, form the 30x30 Hessenberg H, and QR-factor it for its eigenvalues. The Ritz values nearest the right of the complex plane approximate A's rightmost eigenvalues. If you need more accuracy you restart, keeping the directions that captured those rightmost Ritz values.
Arnoldi generalizes Lanczos to nonsymmetric matrices: a long recurrence and a small Hessenberg projection instead of a short recurrence and a tridiagonal one.
Arnoldi keeps and orthogonalizes against ALL prior basis vectors (a long recurrence), so its per-step cost and memory grow with the step count — this is why restarting is essential, and why for symmetric problems you should use Lanczos instead. Convergence for nonsymmetric matrices is less predictable because their eigenvalues may be ill-conditioned.