Conjugate gradient method

An iterative algorithm for solving symmetric positive-definite linear systems. It builds mutually conjugate search directions so the exact solution is reached in at most as many steps as the system has distinct eigenvalues.

Krylov subspace: A subspace spanned by a vector and successive applications of a matrix to that vector. Each iterate lies in a Krylov subspace generated by the matrix and initial residual.
Symmetric positive-definite matrix: A real symmetric matrix whose quadratic form is strictly positive for every nonzero vector. This matrix class guarantees a unique solution and defines the inner product used by the algorithm.
Sparse matrix: A matrix in which most entries are zero. Sparse storage makes each iteration practical for systems with millions of unknowns.
GMRES: An iterative Krylov-subspace method for solving general nonsymmetric linear systems. GMRES handles nonsymmetric matrices, whereas standard conjugate gradients require symmetric positive definiteness.
Cornelius Lanczos: A Hungarian-American mathematician who developed influential numerical methods, including the conjugate-gradient method. Lanczos introduced the method in 1952 as a way to solve linear systems iteratively.
Conjugate directions: Vectors orthogonal under a specified positive-definite matrix inner product. The method chooses search directions that are mutually conjugate with respect to the system matrix.
Quadratic form: A homogeneous degree-two polynomial represented by a vector and a matrix. The system solution is the minimizer of a quadratic energy whose curvature is set by the matrix.
Finite element method: A numerical technique that approximates solutions to differential equations using piecewise-defined basis functions. Its discretized elliptic equations often produce large sparse positive-definite systems.
BiCGSTAB: An iterative method for nonsymmetric linear systems that stabilizes the BiCG recurrence. It targets nonsymmetric problems where conjugate gradients' matrix assumptions fail.
Magnus Hestenes: An American mathematician known for work in numerical analysis and optimization. Hestenes developed and publicized conjugate gradients with Eduard Stiefel.

Linked from 7 pages