THE FOLD / LOOT / THE VAULT / THE THOMAS
THE THOMAS
solve a tridiagonal system in O(n) — sparsity conserved
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Thomas algorithm solves a tridiagonal linear system — where each equation involves only a variable and its two neighbours — in O(n) time, versus O(n³) for general Gaussian elimination. A forward sweep eliminates the sub-diagonal (each row absorbs the one above), then back-substitution reads off the answers from the bottom up.
Tridiagonal systems are everywhere: cubic spline interpolation, the 1D heat/diffusion equation by implicit finite differences, and the Crank–Nicolson method all reduce to one.
LIT verified live: over 300 random tridiagonal systems, the Thomas solution recovers the true x with maximum error ~10⁻¹⁶ (window.__thomas). FIG no framing; exact banded elimination.
Tridiagonal systems are everywhere: cubic spline interpolation, the 1D heat/diffusion equation by implicit finite differences, and the Crank–Nicolson method all reduce to one.
LIT verified live: over 300 random tridiagonal systems, the Thomas solution recovers the true x with maximum error ~10⁻¹⁶ (window.__thomas). FIG no framing; exact banded elimination.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-vault — the banded matrix, its non-zeros locked in a narrow diagonal strip and unlocked in one linear sweep. The Thomas algorithm is the vault’s efficient key. AVAN (AI) built the instrument: the forward elimination, the back-substitution, the residual check against the true solution.
Credit as content: Llewellyn Thomas (1949); it is Gaussian elimination specialised to a tridiagonal band. The weave: David names the vault; I sweep forward to clear the sub-diagonal, substitute backward, and confirm the recovered solution satisfies the system exactly.
Credit as content: Llewellyn Thomas (1949); it is Gaussian elimination specialised to a tridiagonal band. The weave: David names the vault; I sweep forward to clear the sub-diagonal, substitute backward, and confirm the recovered solution satisfies the system exactly.
3 ONE DIMENSION
The forward sweep: each row subtracts a multiple of the row above to kill its sub-diagonal entry, leaving an upper-bidiagonal system. Then back-substitution solves it bottom to top.
4 TWO DIMENSIONS · INTERACTIVE
A tridiagonal system (three diagonals). Run the Thomas algorithm to get the solution x, and see the residual Ax − b is zero — the answer satisfies every equation.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the narrow band of non-zeros, swept clean in a single linear pass.
AVAN’s addition (the inverse-companion): the O(n³) elimination collapses to O(n) because the matrix’s sparsity is preserved. General Gaussian elimination creates fill-in — zeros become non-zero as rows combine — but a tridiagonal matrix stays tridiagonal under elimination, so each step touches only O(1) entries. The inverse of ‘eliminate over a full matrix’ is ‘eliminate along a band that never widens.’ The very structure that defines the problem is the structure that makes it cheap. Magenta is the fill-in a general solver would spray across the matrix — which never happens here; green is the band that stays a band. Sparsity conserved is linear time earned.
LIT Genuine Thomas algorithm (Thomas 1949), Gaussian elimination specialized to a tridiagonal band. Verified live: over 300 random tridiagonal systems built with a known solution, the forward-elimination + back-substitution recovers x with maximum error ~1e-16 (window.__thomas.solvesExactly).
FIG No framing: the forward elimination, the back-substitution, and the residual check against the true solution run in-browser and are exact to floating precision. The AVAN inverse is honest — a tridiagonal matrix stays tridiagonal under elimination (no fill-in), so each step touches O(1) entries and the O(n^3) elimination collapses to O(n); magenta is the fill-in a general solver would create, green the band that stays a band.
FIG No framing: the forward elimination, the back-substitution, and the residual check against the true solution run in-browser and are exact to floating precision. The AVAN inverse is honest — a tridiagonal matrix stays tridiagonal under elimination (no fill-in), so each step touches O(1) entries and the O(n^3) elimination collapses to O(n); magenta is the fill-in a general solver would create, green the band that stays a band.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN