precondition-kappa
At its defaults it draws the condition number a sketched preconditioner leaves, against the condition number it was given. Two curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 4n-row sketch, is 2.2284 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.
precondition-kappa is one function in lib/figures/precond.js —
a sketch as a preconditioner — the same randomness, spent on the cost instead. 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.
Two curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 4n-row sketch, is 2.2284 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.
width: 4
The arguments are the ones A preconditioner that changes sign 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.
Two curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 4n-row sketch, is 2.2284 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.
width: 2
The arguments are the ones Doing it twice 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.
Two curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 2n-row sketch, is 6.1286 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.
width: 10
The arguments are the ones The sketch that is not the answer 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.
Two curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 10n-row sketch, is 1.6616 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.
n: 16
The arguments are the ones The sketch that is not the answer 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.
Two curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 4n-row sketch, is 2.6304 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.
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.
17 distinct claims across 5 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 number of columns the sweep can afford
a sketch wider than the problem and narrower than the data
and is the SAME number at every one of them, not merely a similar one
enough rows for the sketch to be a sketch
matmul shapes agree
the sketch's R factor is nonsingular at κ = 100
the sketch's R factor is nonsingular at κ = 10¹⁰
the sketch's R factor is nonsingular at κ = 10⁴
the sketch's R factor is nonsingular at κ = 10⁶
the sketch's R factor is nonsingular at κ = 10⁸
while κ(A) moves by orders of magnitude
κ(AR⁻¹) is a small constant at κ(A) = 100
κ(AR⁻¹) is a small constant at κ(A) = 10¹⁰
κ(AR⁻¹) is a small constant at κ(A) = 10⁴
κ(AR⁻¹) is a small constant at κ(A) = 10⁶
κ(AR⁻¹) is a small constant at κ(A) = 10⁸
κ(AR⁻¹) measured and κ(SU) computed from the sketch alone agree
Against the rule
It draws a decomposition and prints its residual. It calls
qrHouseholder, sketchPreconditioner,
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 90
of 174 generators —
75 print a residual and
15 are exempt with a published reason;
84 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 preconditioner that changes sign
Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.
Methods that were designed apartAn answer that changes with the seed
A randomised rank-k solve is a truncation computed in a random subspace, and it reaches the same floor as the deterministic ones. What it does not do is return the same answer twice — a factor of 1.84 across four seeds at rank 8, and 1.02 at the rank where the method is best.
Iterating, instead of factorisingAn orthogonalisation nobody calls one
Conjugate gradients are derived as a minimisation and behave as an orthogonalisation, which is why the finite-termination property in every textbook is not a property the method has in floating point.
Iterating, instead of factorisingChanging the condition number on purpose
Preconditioning is usually introduced as a trick that makes an iteration converge faster. It is not a trick. It is solving a different system with the same solution and a condition number chosen rather than inherited, and the new condition number is computable.
Randomised, and the guarantee that changes kindCounting what cannot be looked at
The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.
Where the flop count stopped predicting the timeDoing it twice
Cholesky QR squares the condition number — a fitted slope of 1.95 in κ against the Householder sweep's 1.00. Run the identical routine a second time on the Q it returned and the slope is 0.93, the orthogonality is at or below the sweep's at every κ, and the price is one more all-reduce.
Methods that were designed apartFour knobs and one floor
A truncation, a Tikhonov parameter, a step count and a randomised rank, on one problem with an answer that is known. Their best errors are 0.1445, 0.1406, 0.1426 and 0.1449 — a spread of 3% across four methods that share no arithmetic.
Randomised, and the guarantee that changes kindThe dimension does not appear
A random projection preserves the lengths of a set of vectors to within a distortion that depends on how many vectors there are and not on how many coordinates each one has. That is the fact the whole field rests on, and it is genuinely surprising.
Iterating, instead of factorisingThe formula that was already optimal
Ask for the interpolation that minimises the energy of its own columns and the answer is the classical AMG formula — to zero at every row of the one-dimensional Laplacian, and to four digits in two dimensions. On the operator rotated to 45° the two part company, and the gap between them is a diagnostic that needs no reference solution.
Randomised, and the guarantee that changes kindThe sketch that is not the answer
Sketch-and-solve throws away the original problem and keeps the small one's answer, which is why its answer moves with the seed. Use the same sketch as a preconditioner instead and the condition number the iteration sees is the same number at every κ from a hundred to ten billion — identically the same, to nine digits, because the spectrum cancels out of it.
Orthogonality, measuredTwo Gram–Schmidts
One argument changes. Classical Gram–Schmidt projects the original column onto each previous direction; modified projects what is left of it. In exact arithmetic the coefficients are identical. In floating point they differ by eight orders of magnitude in the thing that matters.