trace-rate
At its defaults it draws two trace estimators against their budget, on a 80×80 matrix whose spectrum decays at 0.85. Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
trace-rate is one function in lib/figures/trace.js —
counting the diagonal without looking — two probes, and one of them is free. 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 of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.85
The arguments are the ones A hierarchy with no grid behind it 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 of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.95
The arguments are the ones A parameter chosen on a smaller problem 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 of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.50 and Hutch++'s is -1.03. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.7
The arguments are the ones Counting what cannot be looked at 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 of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.31 and Hutch++'s is -5.07. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 1
The arguments are the ones Counting what cannot be looked at 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 of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.32 and Hutch++'s is -0.67. With no decay there is no dominant subspace to project out, so the two exponents are the same and the third of the budget Hutch++ spends on a sketch is simply lost.
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.
14 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.
sitting above it at every budget, at s = 12 — asserted 4 times
a decay rate between everything and nothing
a size the repeated sweeps can afford
and Hutch++ does NOT change the exponent when there is nothing to deflate
and Hutch++ falls faster on a spectrum that decays
at an exponent past one
enough seeds for a median
Hutchinson falls like one over the square root of the budget
matmul shapes agree
reaching a smaller error at the largest budget
the spectrum leaves a trace worth estimating
Against the rule
It draws a decomposition and prints its residual. It calls
hutchPP,
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 hierarchy with no grid behind it
On a graph Laplacian the algebraic V-cycle converges at 0.199 a cycle, its grid complexity is an unremarkable 3.05, and its operator complexity is 17.7 — one level of forty-one unknowns is entirely dense. The number people quote is the one that does not measure the work.
Methods that were designed apartA parameter chosen on a smaller problem
Inside a hybrid method the regularisation parameter is chosen on a 25×24 problem rather than a 64×64 one. The rule that reads a residual transfers exactly; the rule that reads a trace is biased by exactly two grid steps at twenty-four steps and one at forty, at every noise level from 10% to 0.1%.
Methods that were designed apartA parameter that counts steps
The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.
Iterating, instead of factorisingA rate that does not notice the size
The V-cycle reduces the residual by a factor of ten a cycle at fifteen points and at a hundred and twenty-seven. Jacobi on the same four problems goes from 0.981 to 0.9978, climbing towards one. One of those is a constant and the other is an exponent, and that is the whole distinction the field turns on.
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 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.
Randomised, and the guarantee that changes kindRandomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.
Eigenvalues, singular values, rankRestarting is a filter
A restart throws away the Ritz values it does not want and begins again from a new starting vector. Written in the eigenbasis, that vector's components have been multiplied by a polynomial with its roots at the discarded values — measured component by component, and agreeing with the polynomial to rounding.
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.
Structure, and the solver that cannot see itTwo dimensions, and the cluster that thins
The same kernel, the same averaging, the same transform — applied along two axes instead of one. In one dimension the preconditioned step count is 7, 10, 10, 10; on square grids with the same unknown counts it is 10, 18, 20, 21, and the share of the spectrum near one falls from 56% to 17%.
The arithmetic underneathWhere the hardware went
bfloat16 carries eight mantissa bits, which puts its refinement threshold at a condition number of 256. That is not an exotic matrix. It is an ordinary one, and past it the method still improves the answer by a factor of four hundred while getting nowhere near a usable one.