← All Base Form Math projects
BM-11NOT STARTEDBASE FORM · LINEAR ALGEBRAMATHPYTHON

Heat-spread simulator

Simulate heat spreading across a metal plate (or smooth a photo) by solving a huge sparse system with conjugate gradient.

EST.7 h
REWARD+100 XP
AFTERoriginal

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
solution and time on a 500×500 grid
GOAL · match within 1e-6; faster than dense solve
scipy.sparse.linalg.spsolve—
no results yet
YOUR RESULTS

Your recorded results appear here.

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 Au=bAu = b, where uu holds the unknown temperatures:

4ui,j−ui−1,j−ui+1,j−ui,j−1−ui,j+1=04u_{i,j} - u_{i-1,j} - u_{i+1,j} - u_{i,j-1} - u_{i,j+1} = 0

Edge temperatures are known, so they move to the right side bb. 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 AA has at most five nonzero entries, so AA is sparse. You only ever need to compute AxAx, 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 r=b−Axr = b - Ax and moves along search directions pkp_k chosen so that pi⊤Apj=0p_i^\top A p_j = 0 for i≠ji \ne j. 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 nn, while Jacobi's grows with n2n^2.

VISUALFig. 1
−1 −1 −1 −1 4 ONE ROW OF A: THE STENCIL 4u(i,j) minus its four neighbours A FOR A 4 × 4 GRID (16 × 16) dark = −1, yellow = 4, blank = 0 at most 5 nonzeros per row
Left: one row of A is the five-point stencil. Right: the full matrix for a 4 × 4 grid. Only five diagonals hold nonzeros. Why it's here: It shows why A is sparse and why a matvec is just a stencil on the grid, which is all CG needs.
HINT · OBJECTIVE 4
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 5
Stuck? Hints stay hidden until you ask.

DATA · generated grids

Objectives

0 / 6 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. 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>"`.
  2. 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.
  3. 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

Smooth a photo: solve (I + λL)u = f, where f is a grayscale image and L is the same stencil matrix. Try several λ and see how the blur grows.
Animate heat spreading over time with implicit Euler: each frame solves (I + αL)u_new = u_old with CG.
Compare your CG with scipy.sparse.linalg.cg and with a multigrid solver from the pyamg package on the 500 × 500 grid.

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.