← All Cracked Math projects
PM-I08NOT STARTEDINTERMEDIATEMATHPYTHONIMPACT ★★☆☆☆

Conjugate gradient on a million-unknown Poisson problem

From 'CG without the agonizing pain' (the title of a well-known conjugate gradient tutorial) to a multigrid preconditioner whose iteration count does not grow with the grid.

EST.12 h
REWARD+300 XP
AFTERJonathan Shewchuk + 1

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Iterations and wall time to reach relative residual 1e-8 (||b - Ax|| / ||b||)
GOAL · Plain CG iterations within 5% of scipy's. IC(0)-PCG (CG with a zero-fill incomplete Cholesky preconditioner) needs >= 3x fewer iterations than CG. Multigrid-PCG iteration count stays flat (+/-20%) from 250^2 to 1000^2.
scipy.sparse.linalg.cg and spsolve (SuperLU) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Conjugate gradient (CG) solves Ax = b for symmetric positive definite (SPD) matrices using only matrix-vector products, improving its guess each iteration. A preconditioner is a cheap approximate inverse that makes the problem easier, so CG needs fewer iterations. Hand-roll CSR/COO sparse storage (formats that store only the nonzero entries) with a vectorised matvec. Implement CG, Jacobi-preconditioned CG (divide by the diagonal), incomplete-Cholesky-preconditioned CG (a Cholesky factorisation that keeps only the original sparsity pattern) and a two-level multigrid preconditioner (remove smooth errors on a coarser grid, where they are cheap to fix). Solve the 5-point Laplacian (the standard grid discretisation of the Poisson equation) on grids up to 1000x1000, which is a million unknowns, and one SPD matrix from SuiteSparse (a public collection of real sparse matrices).

VICTORY CONDITIONS

  1. Plain CG iterations within 5% of scipy's. IC(0)-PCG (CG with a zero-fill incomplete Cholesky preconditioner) needs >= 3x fewer iterations than CG. Multigrid-PCG iteration count stays flat (+/-20%) from 250^2 to 1000^2. (Iterations and wall time to reach relative residual 1e-8 (||b - Ax|| / ||b||)).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Conjugate gradient (CG)
An iterative solver for symmetric positive definite systems that needs only matrix-vector products and converges faster when the matrix is well conditioned.
Preconditioner
An easy-to-apply approximation of the inverse matrix that transforms the system so the iterative solver converges in fewer steps.
Incomplete Cholesky, IC(0)
A Cholesky factorisation that drops every entry outside the original sparsity pattern, giving a cheap approximate factor.
Multigrid
A method that smooths errors on the fine grid and fixes the remaining smooth errors on a coarser grid, so cost per accuracy does not grow with grid size.
Residual
b - Ax for the current guess x; its size relative to b measures how close you are to solving the system.

Why it rates ★★☆☆☆

Standard scientific-computing material, but a grid-independent preconditioner is real craft.