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
- 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||)).
- 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.