Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 38 ยท Projects

Project: Simulate Heat Diffusion with Sparse Solvers

Simulate 2D heat diffusion with a sparse finite-difference Laplacian. Compare explicit and implicit time stepping, use splu, and draw animation frames.

Put a hot coin on a cold metal plate and the heat spreads out until the plate is uniformly lukewarm. The physics is described by the heat equation, a partial differential equation that says the temperature at a point changes at a rate proportional to how different it is from its neighbours. It is also the simplest example of a whole family of simulations (fluids, chemistry, finance) where a grid of numbers is updated step after step.

In this project you will turn the heat equation into a sparse matrix, step it forward in time two different ways, and see for yourself why the second way is the one real simulations use. You need Sparse Matrices and Sparse Linear Algebra and Graph Algorithms; Solving ODEs with solve_ivp gives helpful background on time stepping and stiffness.

flowchart LR
    A["Grid of<br/>temperatures u"] --> B["Sparse Laplacian L<br/>(neighbour differences)"]
    B --> C["du/dt = L u"]
    C --> D["Explicit step<br/>u + dt L u"]
    C --> E["Implicit step<br/>solve (I - dt L) u_new = u"]
    E --> F["splu: factor once,<br/>solve every step"]

From a physical law to code. The implicit branch needs a sparse linear solve at every step, which is why factoring once matters.

From the heat equation to a matrix

On a unit square plate we want the temperature u(x, y, t) with du/dt = alpha * (d2u/dx2 + d2u/dy2). Take alpha = 1 to keep the numbers simple. We put an n by n grid of interior points with spacing h = 1 / (n + 1) and keep the plate edges at temperature 0 (the edges are held cold).

In one dimension, the second derivative at a grid point is approximated by (u[i-1] - 2*u[i] + u[i+1]) / h**2. That is a tridiagonal matrix T with the pattern 1, -2, 1, divided by h**2. In two dimensions we flatten the grid row by row into a vector of n*n values. The neighbours left and right are then adjacent in the vector, and the neighbours above and below are n positions away. The Kronecker product builds exactly this structure:

L = kron(I, T) + kron(T, I), scaled by 1 / h**2.

Each row of L has at most five non-zeros (a point and its four neighbours), so a grid with 2,500 unknowns has a matrix with about 12,000 stored values instead of six million.

Python Build the sparse Laplacian and check it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sine pattern is an eigenvector of the Laplacian, so applying L just multiplies it by -2*pi**2. The numerical matrix reproduces that to within 0.04 percent, with a small error that shrinks as the grid gets finer. That is a good sanity check to keep: a simulation you cannot test against a known answer is a simulation you cannot trust.

A related fact makes verification easy: for the initial condition sin(pi x) sin(pi y) the exact solution of the heat equation is the same shape multiplied by exp(-2 * pi**2 * t). It decays but never changes shape.

Explicit versus implicit time stepping

Once we have du/dt = L u we need a way to march in time. There are two basic recipes with step size dt:

  • Explicit (forward Euler): u_new = u + dt * (L @ u). One sparse matrix-vector product per step. Cheap, but only stable if dt is tiny.
  • Implicit (backward Euler): solve (I - dt * L) @ u_new = u. One sparse linear solve per step. More work per step, but stable for any dt.

The explicit method has a hard limit for the 2D heat equation: dt <= h**2 / 4. Beyond it, tiny wiggles grow at every step until the numbers explode. On a 40 by 40 grid that limit is about 0.00015, and halving h makes it four times smaller. This is the same phenomenon as stiffness in Stiff Systems and Higher-Order ODEs: the Laplacian has eigenvalues that range from about -20 to about -13,000 on this grid, and the fastest mode dictates the step.

The implicit method needs a matrix A = I - dt * L that stays the same at every step (as long as dt is constant). So we factor it once with splu, and each time step costs only a cheap back-substitution lu.solve(u).

Python Explicit vs implicit against the exact answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result shows the trade. The explicit method is accurate with a safe step but needs 420 steps. The implicit method reaches the end in 10 steps with a modest error. And the explicit method with the same large step is useless: a function whose true values never exceed 1 has grown to a maximum of 57 after only 10 steps, and it would keep growing.

The implicit error of about 0.018 is not a bug. Backward Euler is only first-order accurate in time: each time you halve dt, the error halves. We can see that directly, and also try the Crank-Nicolson scheme, which averages the explicit and implicit steps and is second-order accurate: (I - dt/2 * L) u_new = (I + dt/2 * L) u.

Python Accuracy of backward Euler and Crank-Nicolson

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Backward Euler's error halves with each doubling of the number of steps, while Crank-Nicolson is about 30 times more accurate even with five steps. After that its error stalls at roughly 0.0001 to 0.00016, which is the spatial error of the grid. More time steps cannot fix a coarse grid; only a finer h can.

Animating the diffusion

Now the real thing: a plate with a hot disc and a hot square. We step forward with the implicit method and save snapshots. A browser TryIt cannot play an animation file, but a row of frames shows the story just as well, and the same loop would feed matplotlib.animation on your own machine.

The initial temperature is 1 inside the two shapes and 0 elsewhere, which has sharp edges. The implicit method deals with that without any trouble, and the edges melt away within a few steps.

Python Frames of a diffusing hot spot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The peaks drop and widen, and the two shapes slowly merge into one glow. The printed total heat decreases because the plate edges are held at zero and heat leaks out through them. If you wanted an insulated plate instead, you would change the first and last rows of T to a Neumann boundary condition and the total would stay constant.

Going further

  • Different materials: replace the scalar alpha with a grid that varies in space (the matrix is then built from face-centred conductivities) to model a plate made of copper and plastic.
  • Heat sources: add a constant vector s to the right-hand side: (I - dt * L) u_new = u + dt * s.
  • Bigger grids: for a 3D problem direct factorization suffers fill-in. Switch from splu to cg with a preconditioner, as in the earlier sparse lesson, because I - dt * L is symmetric and positive definite.
  • Variable steps: if dt changes, you must refactor. Choose a few step sizes and cache one factorization per size.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the 2D Laplacian built with kron(I, T) + kron(T, I)?

    After the grid is flattened into a vector, one Kronecker term couples horizontal neighbours and the other couples vertical neighbours, giving the five-point stencil.
  2. 2. What goes wrong if you use the explicit method with dt larger than h**2 / 4 for the 2D heat equation?

    That is the stability limit of forward Euler. Fast-changing modes are amplified at every step, so rounding noise explodes. SciPy does not intervene because you wrote the loop yourself.
  3. 3. Why call splu once outside the time loop?

    The factorization is the costly part. With a constant dt, each step only needs the triangular solves that lu.solve performs.
  4. 4. Backward Euler's error halves when dt is halved. Which statement is correct?

    Error proportional to dt is first order. Crank-Nicolson is second order, so its error falls much faster until the spatial error of the grid takes over.
  5. 5. In the frames, why does the total heat decrease over time?

    Zero-temperature (Dirichlet) boundaries act as a heat sink. An insulated boundary would conserve the total.

Summary

  • A finite-difference Laplacian on a grid is a sparse matrix with about five non-zeros per row, built compactly with kron and diags.
  • Test the operator against a case with a known answer, such as sin(pi x) sin(pi y), which decays by exp(-2 * pi**2 * t).
  • Explicit stepping is cheap per step but unstable above dt = h**2 / 4; implicit stepping solves (I - dt*L) u_new = u and is stable for any step.
  • Factor the implicit matrix once with splu and reuse it; for very large grids switch to an iterative solver such as cg.
  • Backward Euler is first order in time; Crank-Nicolson is second order, and both are limited by the spatial error of the grid.
  • Snapshots from the loop make a clear picture of diffusion without needing an animation player.

Next: collect the lessons learned about speed and accuracy in Performance, Accuracy and Common Pitfalls.