Skip to content

Implement Conjugate Gradient (CG) for SPD systems #13

Description

@tec-eli

Description

Implement Conjugate Gradient (CG) to solve symmetric positive-definite (SPD)
linear systems A x = b without explicit factorization.

  • Scope: src/krylov/conjugate_gradient.rs
  • Signature: conjugate_gradient<T>(A: &SymmetricMatrix<T>, b: &Vector<T>, x0: &Vector<T>, max_iter: usize, tol: T) -> Result<Vector<T>, ConvergenceError>

Implementation notes

  • Convergence rate depends on sqrt(κ(A)) — pair with high-condition-number matrices in
    tests to show graceful degradation.
  • Only 4 fixed-size vectors (r, p, Ap, x), zero basis growth — stack-safe, no
    const-generic basis decision needed for this one.
  • Don't try to prove SPD upfront (no cheap general test) — detect operationally (negative/
    ~zero p·Ap mid-iteration) and fail fast.
  • max_iter is a mandatory hard cap, not optional.

Tasks

  • Implement conjugate_gradient<T>(...)
  • Monitor residual each iteration; early exit on convergence
  • Detect non-SPD operationally and return Err, never panic
  • Validate input dimensions (A.rows == A.cols == b.len() == x0.len())
  • Add doc-comment with convergence guarantees and # Examples

Tests

  • Unit tests: small SPD matrices with known solutions
  • Property test: final residual ‖b - A x‖ is small
  • Edge case: 1×1 system
  • Edge case: ill-conditioned matrix (document degradation, not failure)
  • Edge case: non-SPD input returns Err, not NaN/panic

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    featureNew feature or capabilitykrylovKrylov subspace methods

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions