Numerical linear algebra: algorithms, stability, and applications

Core problems and common methods

Central tasks include solving linear systems, computing eigenvalues and eigenvectors, performing least-squares fits, and evaluating matrix functions. Many methods fall into two broad classes: direct factorizations and iterative solvers. Direct factorizations include Gaussian elimination with pivoting (LU), Cholesky for positive-definite matrices, and QR or singular value decomposition (SVD) for least-squares and rank-revealing problems. Iterative methods such as Conjugate Gradient, GMRES, and Lanczos are preferred for very large or sparse systems.

Key concepts in numerical behavior

Analysis in the field emphasizes conditioning of a problem (how input perturbations affect the exact solution) and stability of an algorithm (how rounding and finite arithmetic affect computed results). Backward error analysis is widely used: an algorithm is regarded as good if its output is the exact solution of a nearby problem. Practical measures such as pivoting strategies, orthogonalization, and preconditioning are designed to mitigate growth of rounding errors. For verification and rigorous bounds on numerical results, see research in validated numerics.

Sparse and large-scale computations

When matrices are sparse (most entries zero), specialized storage formats and algorithms exploit that structure to reduce memory and time. Graph-based reorderings, incomplete factorizations, and multigrid methods are standard tools. Large-scale problems also motivate parallel and distributed implementations to use modern multicore CPUs and GPUs efficiently.

History, software and notable contributors

The subject grew out of early computing and mathematical work by figures such as John von Neumann, Alan Turing, and later contributors including James Wilkinson and Gene Golub, who helped establish modern algorithmic practices. Widely used software libraries implement these methods in tuned form: BLAS and LAPACK provide dense linear algebra kernels and factorizations; ARPACK and modern packages supply iterative eigensolvers and large-scale solvers.

Applications and distinctions

Numerical linear algebra underpins scientific computing, engineering simulation, data analysis (for example principal component analysis via SVD), optimization, control theory, and machine learning. It differs from symbolic linear algebra in aiming for approximate answers produced efficiently on finite-precision machines rather than exact algebraic expressions. Advances in algorithms, preconditioning, and hardware-aware implementations continue to expand the range of tractable problems.

Further reading

• Introductory texts and courses in linear algebra and numerical methods.
• Tutorials and references on solving linear systems and eigensolvers for practitioners.