Rodin/Solver/CG.h file

Conjugate gradient solver for symmetric positive definite systems.

This header provides the CG (Conjugate Gradient) solver class, an iterative method for solving linear systems with symmetric positive definite matrices.

Algorithm

The conjugate gradient method solves:

\[ Ax = b \]

where $ A $ is symmetric positive definite. It minimizes the quadratic form $ \frac{1}{2}x^TAx - b^Tx $ using conjugate search directions.

Convergence

CG converges in at most $ n $ iterations in exact arithmetic. The error decreases as:

\[ \|x_k - x^*\|_A \leq 2 \left( \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1} \right)^k \|x_0 - x^*\|_A \]

where $ \kappa $ is the condition number of $ A $ .

Applicability

  • Symmetric positive definite matrices
  • Large sparse systems
  • Elliptic PDEs (Poisson, heat equation, elasticity)
  • Systems amenable to preconditioning

Usage Example

Problem problem(u, v);
problem = Integral(Grad(u), Grad(v)) - Integral(f, v);

Solver::CG solver(problem);
solver.setTolerance(1e-10).setMaxIterations(1000).solve();

if (solver.success())
  std::cout << "Converged!\n";

Namespaces

namespace Rodin
The Rodin library for Shape and Topology Optimization.
namespace Rodin::Solver
Module for linear algebra systems.

Classes

template<class Scalar>
class Rodin::Solver::CG<Math::LinearSystem<Math::SparseMatrix<Scalar>, Math::Vector<Scalar>>>
Conjugate gradient solver for symmetric positive definite sparse systems.
template<class Scalar>
class Rodin::Solver::CG<Math::LinearSystem<Math::Matrix<Scalar>, Math::Vector<Scalar>>>
Conjugate gradient solver for symmetric positive definite dense systems.