Task 3 of 5

Colour the Board

Jacobi throws information away. Halfway through a sweep plenty of neighbours already have better values, and Jacobi ignores every one of them because it reads only the old grid. Gauss-Seidel is the fix a human would reach for: walk the cells in order and always use the newest value available. It converges about twice as fast — and it is sequential by construction. Cell 500 cannot start until cell 499 has finished. There is no thread ordering on a GPU and no way to make one thread wait for another, so the textbook algorithm is simply not on the menu.

The fix is a chessboard. The 5-point stencil only ever reads the four direct neighbours, and on a chessboard every direct neighbour of a red square is black. So call a cell red when (x + y) is even and black when it is odd, and update all the reds at once: no red cell reads another red cell, so there is nothing left to order. Then update all the blacks, reading the reds that were just written — which is exactly the "use the newest value" that made Gauss-Seidel fast. One sequential pass becomes two data-parallel half-sweeps.

This task is the red half. Every thread still writes only its own cell, so black cells are not "skipped" — they gather themselves, unchanged, ready for the half-sweep that is about to need them exactly as they are.

a red cell's four neighbours are all black, so no red waits on a red

Goal: write the red half-sweep — cells with (x + y) % 2 === 0 take their neighbours' average, and every other cell (black cells and the whole boundary) comes through untouched.

Requirements

Boundary cells return u[y][x]
Keep the parity in a number: const parity = (x + y) % 2; — a boolean in a kernel variable does not compile on WebGL
Cells with parity 1 (black) return u[y][x] unchanged
Cells with parity 0 (red) return (left + right + up + down) / 4

Hint 1 — the trap this task is built around

The natural spelling is a boolean, and it is the one thing gpu.js cannot do:

const isRed = (x + y) % 2 === 0;   // throws on WebGL

The GL backend has no way to store a bool in a kernel variable, so it fails at shader-compile time with cannot convert from 'bool' to 'lowp float' — and the CPU backend runs it happily, which is how this reaches production. Keep the number:

const parity = (x + y) % 2;        // 0 or 1
if (parity !== 0) return u[y][x];

Hint 2 — three exits, one average

The kernel is a stack of guards: boundary first, then the wrong colour, then the arithmetic. Whichever way a thread leaves, it writes exactly one cell — its own.

Hint 3 — the whole body

if (x === 0 || y === 0 || x === this.constants.size - 1
    || y === this.constants.size - 1) {
  return u[y][x];
}
const parity = (x + y) % 2;
if (parity !== 0) return u[y][x];
return (u[y][x - 1] + u[y][x + 1]
      + u[y - 1][x] + u[y + 1][x]) / 4;

Same idea elsewhere

Red-black ordering — and its multi-colour generalisation — is the standard way to put a Gauss-Seidel or SOR smoother on a GPU: CUDA and WGSL do exactly this, one dispatch per colour, and unstructured meshes get their colours from a graph-colouring pass first. The idea generalises past solvers: a colour is simply a set of updates guaranteed not to depend on each other, which is the same permission slip a wavefront or a task-graph level hands out.

All tasks in Iterative Linear Solvers

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.