Brief
Heat flows from hot to cold. Hold the edges of a metal plate at fixed temperatures, wait, and the plate settles into a steady state. In that state every interior point is the average of its four neighbours. Write that rule for every point of a grid and you get a linear system , where holds the unknown temperatures:
Edge temperatures are known, so they move to the right side . A 500 × 500 grid gives 250,000 unknowns. You can't
hand that to np.linalg.solve: the dense matrix alone would need 500 GB. But each row of has at most five nonzero
entries, so is sparse. You only ever need to compute , and for this matrix that is the stencil applied to the
grid with a few NumPy slices.
An iterative solver uses exactly that. Jacobi, the simplest one, keeps averaging neighbours. It works, but heat creeps across a big grid one cell per step, so it needs a huge number of iterations. Conjugate gradient (CG) is much smarter. It tracks the residual and moves along search directions chosen so that for . A step along one direction never spoils the earlier ones. For this grid, CG needs a number of steps that grows roughly with the side length , while Jacobi's grows with .
DATA · generated grids
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- On the 500 × 500 grid, your CG solution matches `scipy.sparse.linalg.spsolve` with a max absolute difference under 1e-6. Record it with `python tools/mlarena.py record BM-11 "<max diff>"`.
- Your CG beats a dense solve: measured on grids where the dense matrix fits in memory, and extrapolated to 500 × 500 with the memory figure shown.
- The README shows a heat map made by your solver and a table of iteration counts for Jacobi and CG at each grid size.
Side quests
Terms in plain words
- Iterative solver
- Starts from a guess and improves it step by step, using only matrix-vector products, until the error is small enough.
- Residual
- r = b − Ax: how far the current guess is from solving the system. Zero means solved.
- Conjugate gradient (CG)
- An iterative solver for symmetric positive definite matrices. Each step moves along a new direction that does not undo the progress made along the earlier ones.
- Symmetric positive definite
- A = Aᵀ and xᵀAx > 0 for every nonzero x. CG needs this, and the heat matrix has it.
- Condition number
- For a symmetric positive definite matrix, the largest eigenvalue divided by the smallest. The larger it is, the more steps CG needs.