eigensolvers

An eigensolver is an algorithm or software component that computes eigenvalues and eigenvectors of a square matrix. In the standard eigenproblem, given a matrix A, an eigenvalue λ and a corresponding eigenvector v satisfy Av = λv. In the generalized eigenproblem, Av = λBv, with B a second matrix. Eigensolvers are central to many numerical linear algebra tasks and to scientific computing workflows.

Direct methods attempt to transform A into a form that reveals its spectrum with a finite sequence of operations. Classic algorithms include the QR algorithm and its variants, sometimes after reducing A to an upper Hessenberg form. For symmetric or Hermitian matrices, the problem simplifies and every eigenvalue is real with an orthogonal (or unitary) set of eigenvectors; specialized variants exploit this structure to improve stability and reduce cost. The computational complexity is typically O(n^3) for dense problems, though practical implementations use dominated parts for sparse structures.

For large sparse or structured problems, iterative or Krylov subspace methods are preferred. Examples include the power method, inverse iteration and the Rayleigh quotient iteration for targeted eigenvalues, and Krylov methods such as Lanczos (symmetric) or Arnoldi (general). Implicitly restarted variants (e.g., implicitly restarted Arnoldi) compute a few eigenpairs efficiently. Interior eigenvalues can be found via shift-and-invert techniques. Convergence depends on spectral properties and preconditioning can be important.

Applications span principal component analysis, vibration and stability analysis, quantum mechanics, Markov chains, and spectral clustering. Eigensolvers are implemented in libraries such as LAPACK, ARPACK, SLEPc, and PETSc, as well as high-level environments like SciPy. Practical use requires attention to numerical conditioning, normalization of eigenvectors, and the potential presence of nearly repeated or ill-conditioned eigenvalues.