A tolerance is priced by the problem

Three deliberate zeros, put on one pair of axes, turn out to be three samples of one relationship. A deflation criterion writes a zero into a subdiagonal entry; a drop tolerance discards an entry of an incomplete factor; a truncation discards a singular value. Plotted as the fraction of the work not done against the relative backward error the choice introduces, the three come out with fitted slopes of 0.039, 0.051 and 0.225 of the work a decade, and the widest pair of those is a factor of 5.74 apart. That is the argument the comparison was built for, and this is the essay about how much of it is a statement about a grid nobody chose.

Because the comparison contains exactly one problem. The deflation curve is swept on a fixed symmetric matrix of twenty-four unknowns whose spectrum is known by construction. The truncation curve is swept on a fixed symmetric matrix of forty unknowns whose singular values fall by a factor of 0.6 each. Only the drop curve is measured on something with a size in it: an incomplete Cholesky factorisation of a two-dimensional Poisson grid, and the number of points across that grid is the one parameter the whole picture exposes.

Moving it does something the summary line does not report.

The only knob is on the curve that sets neither extreme #

Sweeping the grid from six points across to fourteen — 36 unknowns to 196 — gives drop slopes of 0.188, 0.040, 0.051, 0.054 and 0.057 of the work a decade. Largest over smallest is 4.76. Over the same sweep the deflation slope reads 0.039 five times and the truncation slope reads 0.225 five times, to the three digits the figure prints, because neither of those two curves has been asked to do anything different.

So one of the three numbers on the figure moves by nearly a factor of five and two of them are frozen. The frozen pair is the pair that matters to the headline: the spread the comparison publishes is the largest slope over the smallest, the largest is the truncation curve’s 0.225 and the smallest is the deflation curve’s 0.039, and the drop curve sits between them at every setting of the slider. The summary statistic is computed entirely from the two curves that have no problem attached. It reads 5.744 at 36 unknowns, at 64, at 100, at 144 and at 196.

That is not a stability result. It is the arithmetic of a maximum over a minimum applied to a set in which the extreme members are held still, and it would read 5.744 if the drop curve had been left out of the figure altogether.

Which two curves agree is decided by the grid #

The interesting reading of a three-curve comparison is not the spread but the pairing: which two of the three behave alike, and what that says about which mechanisms are related. On this figure the pairing is a function of the grid size and nothing else.

At 36 unknowns the drop slope of 0.188 sits within 1.20× of the truncation slope, and a reader would conclude that discarding entries of a factor and discarding singular values are close relatives, with the deflation criterion the odd one out by a factor of five. At 64 unknowns the drop slope is 0.040, within 1.01× of the deflation slope — a pairing so tight it looks like a mechanism — and the truncation curve is now the outlier. At 100, 144 and 196 the drop curve stays on the deflation side, at 1.31×, 1.39× and 1.45× of it.

Two of those three readings are available from the same figure, and the thing that decides between them is how many points were put across a model problem. Nothing about incomplete factorisation, or about the theorem that prices a truncation exactly, changed between the two pictures.

Most of that swing is the fitting rule, not the grid #

A factor of 4.76 in a fitted slope is large enough to be worth taking apart, and taking it apart turns out to matter more than the swing itself.

The fit keeps every swept stop whose accepted error is above 10⁻¹⁶, which is there to stop the regression being anchored by points that are measuring the arithmetic’s own rounding rather than the tolerance’s effect. Two of the drop sweep’s eight stops are exactly such points: at a tolerance of zero, and at 10⁻⁶ on the smaller grids, nothing is dropped at all and the reported error is the Frobenius residual of an exact Cholesky factorisation, which is rounding and nothing else.

At 36 unknowns that residual is 9.58·10⁻¹⁷ and at 64 unknowns it is 1.12·10⁻¹⁶. They are sixteen per cent apart and they lie on opposite sides of 10⁻¹⁶. So the fit at 36 unknowns sees six stops spanning 4.35 decades of accepted error, and the fit at 64 unknowns sees eight spanning 15.58 decades, with the two extra points pinned at zero saving sixteen decades to the left. That is the whole of the collapse from 0.188 to 0.040.

Fitting the same eight stops at every grid gives 0.034, 0.040, 0.051, 0.054 and 0.057, a swing of 1.65 rather than 4.76, and it is monotone: a larger grid does buy a steeper trade, which is the effect the slider’s note describes and which the figure’s own numbers obscure. The drop tolerance’s exchange rate genuinely improves with the size of the problem, by about two thirds across a factor of 5.4 in the number of unknowns, and the drawn version of that finding is a non-monotone jump five times too large followed by a slow climb.

There is one further consequence of the uniform fit, and it is the only place in this essay where the published number moves at all. Under it the drop slope at 36 unknowns is 0.034, which is below the deflation curve’s 0.039 rather than between the two, so the drop curve becomes the minimum and the reported spread reads 6.56 instead of 5.744. At the other four grids it is 5.744 exactly, as before. A statistic that is insensitive to the only parameter in the comparison and sensitive to a threshold in how the comparison is fitted is reporting on the fitting.

What the same tolerance actually costs #

The slopes are what the figure prints. What a caller sets is a tolerance, and the useful question is what one fixed tolerance buys on one problem and on another.

At a drop tolerance of 0.01, the incomplete factor keeps 137 of the exact factor’s 221 entries at 36 unknowns and 873 of 2,757 at 196 — 38.0 per cent discarded against 68.3 per cent, for backward errors of 1.21·10⁻² and 1.48·10⁻². Nearly the same error, nearly twice the saving. In iterations the improvement is in the same direction: the preconditioned solve takes 7 steps against 19 unpreconditioned on the small grid and 12 against 51 on the large one, so the fraction of iterations not taken rises from 63.2 per cent to 76.5 per cent.

At a tolerance of 0.001 the same pattern is sharper still: 10.4 per cent of the factor discarded at 36 unknowns and 39.1 per cent at 196, for errors of 1.17·10⁻³ and 1.78·10⁻³. The same constant is a materially better offer on the larger problem, in both currencies at once, which is the sense in which a tolerance is priced by the problem rather than chosen against a scale.

That last point is worth naming, because it is the one the drop curve’s fit leans on hardest at every grid. At a tolerance of 0.3 the entire strict lower triangle goes, the factor is diagonal, and the preconditioned iteration takes exactly the unpreconditioned step count at every grid size tried: 19 against 19, 29 against 29, 36 against 36, 44 against 44, 51 against 51. Its reported saving nevertheless climbs from 83.7 to 92.9 per cent as the grid grows, because a diagonal is a smaller fraction of a denser factor. The rightmost point on the drop curve is a preconditioner that does nothing to the condition number, and it gets more impressive-looking on every larger problem.

Where it stops being true: the fixed curves are frozen, not fixed #

The reading so far is that two of the three curves have no size in them. That is true of the figure and false of the underlying families, and the difference is the whole finding.

The truncation sweep has a size. Fitted on symmetric matrices of 20, 30, 40, 50, 60, 80 and 100 unknowns, its slope is 0.4508, 0.3005, 0.2254, 0.1803, 0.1503, 0.1127 and 0.0902 of the work a decade. Multiplied by the size, every one of those is 9.0152. The slope is not a measured property of low-rank approximation at all; it is a constant over the number of unknowns, and the constant is 2·log(10)/log(1/0.6) = 9.0152, where 0.6 is the ratio the test matrix’s singular values were built to decay by. Sweeping the decay instead confirms it: at 0.4, 0.5, 0.6, 0.7 and 0.8 the fitted slopes are 0.1256, 0.1661, 0.2254, 0.3228 and 0.5159, and the closed form reproduces all five to four decimals.

That leaves the published spread resting on a number with two arbitrary parameters in it. Against the deflation slope, the ratio is 11.49 on a twenty-unknown matrix, 5.74 on the forty-unknown one the comparison happens to use, and 2.87 on an eighty-unknown one. A factor of four, from a size that appears nowhere in the caption, on the curve whose slope sets the top of the reported spread.

The deflation curve is the honest one of the three, and only in the first of two respects. Fitted at 12, 16, 20, 24, 28, 32 and 40 unknowns its slope reads 0.0407, 0.0359, 0.0386, 0.0392, 0.0405, 0.0378 and 0.0402 — a spread of 1.13 across a factor of 3.3 in size, which is genuine size-independence and is what a reader would want the other two to have. But it moves with the range the tolerance was swept over: fitted on stops from 10⁻¹⁶ to 10⁻² it is 0.0392, from 10⁻¹² to 10⁻² it is 0.0369, from 10⁻⁸ to 10⁻² it is 0.0332, and extending the loose end by one decade to 10⁻¹ makes it 0.0519. That is a spread of 1.56 from a list of tolerances somebody typed.

So the comparison’s least problem-dependent quantity is the one it lets a reader move, and its most problem-dependent quantity is one of the two it holds still. The drop slope varies by 1.65 across a factor of 5.4 in problem size, once fitted consistently. The truncation slope varies by exactly 4.00 across a factor of 4 in matrix size, and by 4.11 across the decay range, and both of those parameters are frozen at values chosen when the sweep was written. A picture whose one slider moves the smallest of the three effects is not a picture of the relationship’s stability, and the number it publishes is the one number in it no parameter on the page can touch.

An agreement that does not move when the problem does #

The contrast worth having is an agreement on this site that survives the same treatment, because the difference is exactly the property the comparison above was assumed to have.

Three unrelated computations accumulate error as the square root of whatever they accumulate against, at fitted slopes of 0.486, 0.554 and 0.507, spread 0.067. Widening the window from two decades to five changes how much of each series is drawn and how far the linear bound has run away by the right edge — a factor of 100 at four decades — and changes none of the three slopes, because they are properties of the measurements rather than of the window. That figure’s own readout carries the word invariant beside the numbers, so a reader dragging it is told which quantities the control governs and which it does not.

That is what a robust agreement looks like when it is stated: a claim about three mechanisms, a parameter that could have broken it, and a report that it did not. The essay that made it is comparing three exponents rather than three ratios of fitted slopes, and an exponent of a half is a statement about a random walk that neither of its three problems can be tuned into.

The three-tolerance comparison is not that, and the honest form of its finding is narrower. Three deliberate perturbations trade backward error for work with the same sign and within about an order of magnitude in slope, on the particular problems each was swept on. The sign is a real result and it is the one worth carrying: every one of the three buys work with error rather than the reverse, monotonically, on every problem tried here. The factor of 5.74 is not a result at all.

The refusal #

The assertion behind this page is fed a truncation tolerance of two.

At that value no singular value survives the comparison — the largest is 1.0 times the largest, and 2.0 times it is larger than anything — so the honest rank is zero and the honest relative error of a rank-zero approximation is exactly one, by definition rather than by measurement. What the sweep reports instead is a rank of one, because the rank is clamped up from zero, with a saving of 0.9500 and an accepted error of 0.600. That last number is the decay ratio the test matrix was built from: repeating it at decays of 0.5 and 0.7 gives accepted errors of 0.500 and 0.700 exactly.

The point is undetectable from the curve. Appending it to the truncation sweep leaves the fitted slope at 0.225379, unchanged to six digits, because saving 1 − 2k/n against an error of 0.6ᵏ is a straight line and the clamped point lands on it. No residual, no monotonicity check and no goodness-of-fit reading would flag it, which is why the guard has to be an assertion that refuses the input rather than a statistic computed from the output.

And it is the same defect as the essay’s subject, one level down: a number on an axis that is a parameter of the test problem wearing the clothes of a measurement. The refusal keeps one such number off the curve. Nothing keeps the size of the matrix off the slope.

What follows for anything that reads a comparison like this #

Check which quantity the control actually moves. A figure with one slider invites the reading that the slider is the comparison’s degree of freedom, and here it is the smallest of three. The same trap is what a parameter chosen on a smaller problem is about from the other side — a rule calibrated where it can be afforded and used where it cannot.

Read a spread as a statement about its extremes, not about its members. Max over min is insensitive to everything between, and a comparison that varies an interior member and reports the spread is reporting a constant. Where several knobs are genuinely varied against each other on one problem with a known answer, as in four knobs and one floor, the spread is a measurement; here it is arithmetic.

Ask what fixes a slope before quoting it. The truncation slope’s 9.0152 divided by a size is the sharpest available instance: two numbers chosen when a test matrix was written, and a fitted result that is their quotient. That is the same shape as a constant that turns out to belong to the machine rather than to the algorithm it was quoted about.

A fitting floor is a modelling choice, not hygiene. Discarding points below 10⁻¹⁶ is defensible and it discarded a different number of points at different grids, which turned a monotone 1.65 into a non-monotone 4.76 pointing the wrong way at its largest step. A cut applied to a quantity that straddles it is a cut applied unevenly.

And a drop tolerance is worth more on a bigger problem. That is the actionable half. The exact factor of a sparse matrix is not sparse and the fill is what makes it not sparse, so a larger grid has more to discard and the same constant discards a larger fraction of it — 38.0 per cent at 36 unknowns and 68.3 per cent at 196, for backward errors within 1.22× of each other. The elimination order changes that count too, and by more than the tolerance does at the tight end: the natural order’s 1,739 entries on the 144-unknown grid come down to 1,026 by renumbering alone, exactly, with no error accepted at all.

Which is the last thing the comparison flattens. Two of its three curves buy work with error and have no alternative; the drop curve has a free saving available first, from an ordering, and only then a priced one. A trade drawn without it prices the whole factor as though the ordering had already been chosen well, and on the natural order it has not.

That distinction is why the detection thresholds are a different subject from these, and why rank is a decision rather than a measurement: an offer can be priced, and a price is only meaningful against a problem. This site has one cost curve whose exchange rate improves as it is pushed — the last digit is the cheapest — and the drop tolerance is a second, quietly, on every larger grid. Neither of those facts is visible in a spread of 5.74.