tolerance-obtained
At its defaults it draws the accuracy asked for, against the accuracy obtained, for two kernels on one partition. ε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 29 times smaller than the tolerance asked for; for log r on the identical partition it is 13 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 112 and would put the curves on the other side of the diagonal.
tolerance-obtained 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.
ε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 29 times smaller than the tolerance asked for; for log r on the identical partition it is 13 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 112 and would put the curves on the other side of the diagonal.
n: 128
The arguments are the ones A block nobody can call sparse 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.
ε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 36 times smaller than the tolerance asked for; for log r on the identical partition it is 30 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 46 and would put the curves on the other side of the diagonal.
n: 256
The arguments are the ones A nearby problem of the wrong kind 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.
ε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 29 times smaller than the tolerance asked for; for log r on the identical partition it is 13 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 112 and would put the curves on the other side of the diagonal.
n: 64
The arguments are the ones Which pairs are allowed to be small 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.
ε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 57 times smaller than the tolerance asked for; for log r on the identical partition it is 46 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 16 and would put the curves on the other side of the diagonal.
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.
15 distinct claims across 4 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.
a partition rule this file defines
a power of two, so the bisection is exact at every level
a shift inside the range the matrix stays positive definite and the geometry stays the geometry
a size the dense reference below is affordable at
a size the sweep is affordable at
an accuracy, not a rank
an admissibility constant inside the range the expansion converges over
and the factor belongs to the kernel rather than to the partition, which is the same partition in both
matmul shapes agree
the assembled error is below the per-block tolerance at ε = 0.01
the assembled error is below the per-block tolerance at ε = 10⁻¹⁰
the assembled error is below the per-block tolerance at ε = 10⁻¹²
the assembled error is below the per-block tolerance at ε = 10⁻⁴
the assembled error is below the per-block tolerance at ε = 10⁻⁶
the assembled error is below the per-block tolerance at ε = 10⁻⁸
Against the rule
It draws a decomposition and prints its residual. It calls
represent, errorAgainstEps,
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 block nobody can call sparse
A 96 × 96 block of a kernel matrix has ninety-six nonzero singular values and five that matter. It has no zero entries, it is not described by fewer numbers than it contains, and neither of the two ways this collection already knows to make a large matrix affordable applies to it.
Structure, and the solver that cannot see itA nearby problem of the wrong kind
A good algorithm returns the exact answer to a nearby problem. A hundred and eighteen essays have measured the distance and not one has asked what the nearby problem looks like. On a Toeplitz system it is a rank-one matrix that is constant along none of its diagonals — and the smallest one that is Toeplitz is two and a half million times larger.
Neither sparse nor denseA 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.
Two errors, and whose fault they areA small residual is not a small error
Substituting the answer back and finding that it fits is the most natural check there is, and it verifies the wrong thing. A residual of 10⁻¹⁷ is entirely compatible with an answer whose second digit is wrong.
Two errors, and whose fault they areAn accuracy that is a backward error
Every backward error on this site is something an algorithm produced and somebody then measured. This one is a line in the program. Solving with a compressed matrix gives a residual that is the compression's own error, at a slope of 1.000 over ten decades, so the knob that sets the storage sets the backward error directly.
Two errors, and whose fault they areAn estimate that can be fooled
Nobody computes a condition number, because forming an inverse costs more than the solve did. Every library estimates it instead, from four or five products with a factorisation already in hand. The estimate is exactly right on four random matrices out of five — and there is a matrix, three distinct entries wide, on which it returns a twentieth of the truth.
Eigenvalues, singular values, rankSmall compared to what
This site's own singular value routine has carried a sentence since the month it was written — that one-sided Jacobi computes the small singular values to high relative accuracy and the standard method does not. It has never been measured here, because measuring it needs a σ that is known rather than computed. A bidiagonal matrix and a Sturm count in exact rationals supply one.
Structure, and the solver that cannot see itThe condition number of the model
Describe a 40×40 Toeplitz matrix by its 1,600 entries and its condition number is 78,800. Describe it by the one number it actually contains and the condition number is 61.9. The three decades in between are not an approximation or a bound — they are what κ has been over-stating, and the drop is not where the linear algebra is.
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.
Regularisation, and the answer that is chosenWhen the answer is a choice
A backward-stable least-squares solve of this problem returns an answer whose relative error is 5.5·10⁸. Nothing went wrong. The singular values decay exponentially with no gap anywhere in them, the data does not determine the answer, and something outside the data has to choose — which is the computation rather than a preliminary to it.
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.