Overview
Preconditioned Conjugate Gradient transforms the system with an easier approximate inverse so conjugate-gradient directions converge in fewer iterations.
CoreSource checked
Preconditioned Conjugate Gradient
Solves symmetric positive definite systems faster by applying a preconditioner.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Advanced
- Family
- Iterative Linear Solver
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
preconditionerresidualconjugate directionsymmetric positive definite matrix
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(iterations * (nnz + preconditioner))
Worst
O(iterations * (nnz + preconditioner))
Space
O(n)
When to Use
- Use when solving equations needs preconditioner.
- Use when the input matches the assumptions behind iterative Linear Solver.
When Not to Use
- Avoid when the problem is ill-conditioned and no scaling or stability checks are available.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Solves symmetric positive definite systems faster by applying a preconditioner
- Uses preconditioner and residual to guide the work.
- Produces approximate numeric result.
Use Cases
- Solving equations
- Approximating integrals
- Working with matrices and differential equations
Inputs
- Numeric function, matrix, or sampled data
- Initial estimate or discretization
- Tolerance
Outputs
- Approximate numeric result
- Error estimate or residual
Key Formulas (1)
Preconditioned residual
M z = r
M z = rApplies the preconditioner by solving an easier system for the search update.
Pseudocode
- 1.Prepare the inputs and state needed for Preconditioned Conjugate Gradient.
- 2.Apply the preconditioner step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return approximate numeric result.
Canonical Example
- Input
- Preconditioned Conjugate Gradient input with a small representative case
- Output
- Approximate numeric result
- Explanation
- Preconditioned Conjugate Gradient applies preconditioner to produce approximate numeric result.
Implementation Notes
- Check convergence with residuals or estimated error, not iteration count alone.
- Keep the preconditioner step separate enough to test independently.
Common Pitfalls
- Ignoring conditioning and residuals can produce plausible-looking but wrong numeric answers.
- Forgetting to check edge cases can make Preconditioned Conjugate Gradient look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow the numeric approximation improving against the target function, matrix, or state.
Step 1 of 4: Prepare the inputs and state needed for Preconditioned Conjugate Gradient.
numerical-methods-mechanismNotes
Preconditioned Conjugate Gradient should be used with the assumptions and tradeoffs of iterative Linear Solver in mind.
Sources (1)
What each reference supports for this entry.
Templates for the Solution of Linear Systems
BookNetlib reference covering preconditioned Krylov methods including PCG.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofConjugate Gradient
PCG is Conjugate Gradient with a preconditioner.
Often paired withMultigrid Method
Multigrid can act as a preconditioner or complementary solver.
Related Algorithms
Tags
Numerical MethodsIterative SolverLinear AlgebraPreconditioning