Conjugate Gradient Method¶
A Krylov-subspace solver for symmetric positive-definite linear systems that builds mutually A-conjugate directions while minimizing the associated quadratic.
Core Idea¶
The conjugate gradient method (CG) solves a linear system \(Ax=b\) when \(A\) is symmetric (Hermitian in the complex formulation) and positive definite. Equivalently, it minimizes the strictly convex quadratic
whose gradient is \(Ax-b\). Starting from \(x_0\), CG builds iterates in expanding Krylov subspaces and chooses search directions that are mutually \(A\)-conjugate: \(p_i^TAp_j=0\) for \(i\ne j\).
The identity is the coordinated recurrence linking the residual, step length, and conjugate direction. In exact arithmetic it reaches the solution in at most \(n\) steps for an \(n\)-dimensional system, and often fewer according to the relevant minimal polynomial/eigenvalue structure.
Scope of Application¶
CG is central in numerical linear algebra, scientific computing, optimization, finite-element and finite-difference PDE discretizations, graph Laplacian problems after suitable handling of nullspaces, and inner solves in larger algorithms. Its economy is especially valuable for large sparse matrices because each iteration primarily needs a matrix-vector product, vector operations, and a small number of inner products.
The method also extends naturally to self-adjoint positive-definite operators in Hilbert-space formulations, subject to analytic and discretization conditions. Its usefulness depends on conditioning and spectrum, not sparsity alone. Dense SPD systems can use CG, while a sparse but nonsymmetric or indefinite system violates the core assumptions.
Clarity¶
The abstraction unifies a solver view and an optimization view. The equation residual \(r_k=b-Ax_k\) is the negative gradient of \(\phi\); solving the system and minimizing the quadratic are the same task under SPD assumptions. The \(A\)-inner product explains “conjugate”: directions need not be Euclidean-orthogonal, but their cross terms vanish in the quadratic geometry.
Manages Complexity¶
CG compresses an expanding optimal subspace method into a three-term recurrence. It avoids storing every prior direction because exact conjugacy makes old correction components remain settled. This gives low memory and exploits sparse matrix-vector products, while retaining a polynomial/Krylov interpretation of convergence.
The compression deliberately leaves the spectrum, conditioning, rounding error, preconditioner, and stopping test explicit. A clustered spectrum can yield rapid convergence; a large condition number can slow it.
Abstract Reasoning¶
With \(r_0=b-Ax_0\) and \(p_0=r_0\), the standard unpreconditioned recurrence is
Under SPD/exact-arithmetic assumptions, \(x_k\) minimizes \(\phi\) over \(x_0+\mathcal K_k(A,r_0)\); residuals are mutually orthogonal and directions mutually \(A\)-conjugate.
Knowledge Transfer¶
Literal transfer occurs across SPD systems when operator application, inner product, residual, and conjugacy are preserved. A finite-element stiffness solve and a covariance-like quadratic optimization can share the same CG core after mapping their matrices and right-hand sides. Preconditioning knowledge transfers by matching which spectral modes are difficult rather than copying a preconditioner blindly.
Transfer to nonlinear conjugate gradient is partial and explicitly variant-level. Transfer to GMRES, Lanczos eigenvalue methods, and LOBPCG occurs through Krylov concepts, but their objectives and invariants differ.
Relationships to Other Abstractions¶
Current abstraction Conjugate Gradient Method Domain-specific
Parents (1) — more general patterns this builds on
-
Conjugate Gradient Method is a kind of Optimization Prime
CG directly instantiates Optimization because each iterate minimizes a convex quadratic over an expanding affine Krylov subspace.
Hierarchy path (1) — routes to 1 parentless root
- Conjugate Gradient Method → Optimization
Neighborhood in Abstraction Space¶
Conjugate Gradient Method sits in a sparse region of the domain-specific corpus (78th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Applied Linear & Special Functions (18 abstractions)
Nearest neighbors
- Quadratic Space — 0.83
- Carlyle Circle — 0.82
- Siegel Zero — 0.82
- Dispersion Function — 0.82
- Jacobi Method — 0.82
Computed from structural-signature embeddings · 2026-09-08