storage-size
At its defaults it draws numbers stored per unknown, against the size of the matrix, at 10⁻⁸. The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 54, 79, 106, 133 and 50, 70, 94, 120, adding about 26 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 26 and 23 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.55, 1.42, 1.33, falling towards one and never arriving, which is what a logarithm looks like from inside.
storage-size is one function in lib/figures/hodlr.js —
the partition — a rule that reads four numbers a pair and no entry of the matrix. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 54, 79, 106, 133 and 50, 70, 94, 120, adding about 26 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 26 and 23 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.55, 1.42, 1.33, falling towards one and never arriving, which is what a logarithm looks like from inside.
logEps: -8
The arguments are the ones A rank that is a number of digits passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 54, 79, 106, 133 and 50, 70, 94, 120, adding about 26 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 26 and 23 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.55, 1.42, 1.33, falling towards one and never arriving, which is what a logarithm looks like from inside.
logEps: -12
The arguments are the ones A rank that is a number of digits passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 60, 94, 131, 170 and 60, 88, 120, 156, adding about 37 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 33 and 30 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.65, 1.48, 1.37, falling towards one and never arriving, which is what a logarithm looks like from inside.
logEps: -4
The arguments are the ones A rank that is a number of digits passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 48, 64, 80, 96 and 36, 48, 62, 76, adding about 16 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 19 and 15 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.42, 1.32, 1.26, falling towards one and never arriving, which is what a logarithm looks like from inside.
logEps: -2
The arguments are the ones The accuracy worth paying for passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 45, 57, 67, 78 and 28, 34, 42, 50, adding about 11 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 15 and 10 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.33, 1.25, 1.21, falling towards one and never arriving, which is what a logarithm looks like from inside.
logEps: -10
The arguments are the ones The size the rank does not notice passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 57, 87, 118, 151 and 56, 80, 108, 140, adding about 31 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 30 and 27 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.60, 1.45, 1.35, falling towards one and never arriving, which is what a logarithm looks like from inside.
What it checked while drawing
Every figure above asserted its own claims on the way to being drawn, and a claim that failed
would have failed the build rather than drawn a wrong picture. Those assertions used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
6 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
and every size is still the matrix at n = 64 — asserted 4 times
an accuracy the blocks have singular values across
the storage per unknown grows by a constant per doubling, which is a logarithm
Against the rule
It draws a decomposition and prints its residual. It calls
storageAgainstSize,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
Across the library: the rule bites on 141
of 264 generators —
126 print a residual and
15 are exempt with a published reason;
123 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A rank that is a number of digits
Ask a kernel block for two digits and it costs two columns; ask for fourteen and it costs nine. The curve is a straight line at 0.55 columns a decade, and the bound the geometry gives is a straight line too — at 3.32, which is the same shape and six times the price.
Randomised, and the guarantee that changes kindBuilt from products alone
A 512-square hierarchical representation, at a relative error of 4·10⁻⁷, from 256 applications of an operator that is never assembled. The compression route reads 262,144 entries; this one reads none, and pays for it with a factor of seven against the representation the entries would have given.
Where the flop count stopped predicting the timeMemory bought with messages
Holding four copies of the data instead of one is supposed to cut a matrix multiplication's communication by √4. Measured on a machine of 64 processors it costs 14% more traffic; at 576 it saves 44%, which is 72% of what the law promises. The memory is exactly four times, and that part is not asymptotic.
Neither sparse nor denseThe accuracy worth paying for
Used as a preconditioner, a hierarchical representation gets better at every accuracy — the iteration count falls monotonically all the way to the tightest tolerance. The total work does not. Its minimum sits at a rank-one preconditioner on an easy problem and six decades further along on a hard one.
Neither sparse nor denseThe kernel with nothing to compress
Hold the geometry fixed at q = ½, fix the wavelength, and scale the picture up by sixteen. A smooth kernel needs six columns at every scale. An oscillatory one needs twelve, sixteen, twenty-two, thirty-three, fifty-three, and there is no scale at which it stops.
Structure, and the solver that cannot see itThe matrix that is one row
A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly. An eigensolver spends a sweep of Jacobi rotations over 256 entries arriving at the same answer, and agrees to 1.2·10⁻¹⁵.
Neither sparse nor denseThe rounding that was not the problem
A rank-k block plus a rank-k block is a rank-2k block, exactly, so every arithmetic in this format truncates after every addition. A Cholesky performed inside it does ninety-eight of those and its residual is 1.14·10⁻⁹ against a representation error of 1.40·10⁻⁹ — the roundings cost nothing measurable.
Where the flop count stopped predicting the timeThe same arithmetic at a different price
A blocked and an unblocked elimination perform 72,568 operations each — the same operations, associated differently — choose the same pivots, and return a factorisation identical to the last bit: ‖PA − LU‖/‖A‖ = 4.487946226420872·10⁻¹⁶ in both. One of them moves 41,332 words between fast and slow memory and the other moves 19,476.
Neither sparse nor denseThe same matrix, numbered twice
One symmetric permutation. The condition number is 24.3948 either way to eight digits and the Frobenius norm is 6.13996414·10³ either way to twelve. The partition that stored 27,008 numbers now finds no admissible pair anywhere and stores all 65,536, and the format that compresses regardless stores 118,208.
Neither sparse nor denseThe size the rank does not notice
Sample a kernel block at 32, 64, 128 and 256 points a side and it needs five columns, five, five and five. Sample the touching block next to it at the same four sizes and it needs nine, eleven, twelve and thirteen. Same kernel, same accuracy, one number and a logarithm.
Neither sparse nor denseThe test that costs what it saves
The partition that refuses to compress a touching pair keeps every rank at five while the other lets them climb from nine to thirteen. It also stores more numbers at every size measured — 67,968 against 61,440 at n = 512 — and which of those two facts matters is a question about how large the problem is going to get.
Where the flop count stopped predicting the timeWhere the format starts paying
A hierarchical solve costs 1.48 times a dense factorisation at 64 unknowns and 0.16 times it at 512. The crossover is between 64 and 128, it walks right when the accuracy is tightened, and the exponent between consecutive sizes is 2.13, 1.93, 1.74 — falling towards one and never arriving.
Neither sparse nor denseWhich pairs are allowed to be small
A hierarchical representation is a partition of the matrix into blocks, and the rule that produces it reads four numbers per pair of index clusters and not one entry of the matrix. On a 256-square it yields 112 blocks, 66 of them stored as two thin factors, none of rank above five.