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 finite element methods and shape optimization.
namespace Rodin::FormLanguage
Module for writing high level abstract expressions.
namespace Rodin::Solver
Module for solving linear and nonlinear 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.