The zero you are allowed to write

Every essay in this collection’s current run has been about a quantity going to zero on its own: a divisor vanishing, a curvature changing sign, an eigenvalue leaving for infinity, a determinant that was identically zero before anybody looked.

This one is about the other half, and it is the half a program actually contains. A zero is never met in floating point. It is declared. Every one of those events reaches the code as a comparison against a constant, and somebody chose the constant.

Three of them, in three vocabularies #

The deflation criterion. The QR algorithm splits its problem when a subdiagonal entry is small compared with its neighbours, and continues on the smaller block. Deflation is what makes the whole algorithm affordable — without it every iteration would cost the full n² however much had already converged — and it works by writing a zero into a matrix entry that is not zero.

The drop tolerance. An incomplete factorisation keeps a factor sparse by discarding entries that are small. The exact factor of a sparse matrix is not sparse — the fill is the subject of a whole field here — so an incomplete one keeps a chosen subset, and the entries not kept are set to zero.

The truncation. A low-rank approximation keeps the k largest singular values and discards the rest, which is setting n − k singular values to zero — and the best approximation there is prices exactly that.

What they have in common #

Each of them is a perturbation of the problem, chosen deliberately.

The deflated matrix is not the matrix that was handed over; it differs from it by whatever was written into that subdiagonal entry. The incomplete factor is the exact factor of nothing; ‖A − LLᵀ‖ is what was discarded and it is not rounding. The truncated matrix is not the matrix; it differs by σₖ₊₁.

So all three are backward errors that somebody chose, in a subject where every other backward error is something the arithmetic did. And that reframing is what makes them comparable, because a backward error is a backward error whatever produced it.

The other axis is what the choice bought: iterations not taken, entries not stored, storage not used.

Which of them is the odd one out #

Before the comparison, one distinction that the comparison would otherwise flatten.

Two of the three tolerances are chosen by a library author and one is chosen by the caller. The deflation criterion is buried in an eigensolver — a caller can rarely reach it and would not know what to set it to. The drop tolerance is an argument to every incomplete factorisation routine there is, with a default the caller usually keeps. The truncation is entirely the caller’s: choosing a rank is what a low-rank approximation is.

That is a distinction about visibility rather than about mathematics, and the mathematics is what this essay compares. It matters afterwards, though, because it says where the finding is actionable. A caller who understands that a rank is a decision and that the decision is a backward error can price it; a caller who understands that a deflation criterion is one has learned something about a number they cannot change.

What they can do with it is read a result differently. An eigenvalue returned by a library is the exact eigenvalue of a matrix perturbed by the deflation criterion as well as by the rounding, and the first of those is usually the larger — which is the exact answer to a nearby problem with the nearness set by a constant rather than by the arithmetic.

One curve #

Sweeping each tolerance over its useful range and plotting the fraction of the work not done against the relative backward error accepted:

• deflation criterion: from 6.7·10⁻¹³ of error and no saving, to 6.6·10⁻² of error and 55 per cent of the iterations not taken;
• drop tolerance: from the unit roundoff and no saving, to 0.43 of error and 90 per cent of the factor’s entries not stored;
• truncation: from 6.2·10⁻⁹ and a negative saving, to 7.8·10⁻² and 75 per cent of the storage not used.

Fitted slopes, in fraction of the work saved per decade of error accepted: 0.039, 0.051 and 0.225. Three fields, no shared arithmetic, no shared vocabulary, and the widest pair of those is a factor of 5.7 apart.

Nothing is rescaled to make that happen. The two quantities are defined the same way for all three because they are the same two quantities, and the agreement is what comes out.

The negative end nobody plots #

The low-rank curve goes below zero at the tight end, and that is worth a sentence because it is the part of the trade that gets left off.

A symmetric n×n matrix is n(n+1)/2 numbers. A symmetric rank-k factored form is k(n+1). So the factored form costs more than the matrix once k passes n/2, and at a tolerance tight enough to keep most of the spectrum the “low-rank approximation” is a more expensive object than the thing it approximates.

Every plot of approximation error against rank stops before that point. It is not wrong to stop there — nobody would use a rank-37 approximation of a 40×40 matrix — but the omission is what makes the trade look like a free lunch at the tight end rather than a bad deal.

Why the slopes are not identical, and why that is the right result #

A factor of six between the slopes is not agreement to three digits, and reading it as one would be overclaiming.

What the three share is the sign and the order of magnitude: in each field, one decade of accepted error buys somewhere between four and twenty-two per cent of the work. What differs is how much structure each problem has for the tolerance to exploit.

The truncation slope is the steepest because a decaying spectrum is the most compressible thing on the list — one decade of tolerance discards many singular values when the decay is geometric. The deflation slope is the shallowest because the subdiagonal entries the criterion is testing are falling quadratically once convergence starts, so a decade of tolerance moves the deflation point by only a step or two.

Both of those are statements about the problem. Which is the useful form of the finding: the trade exists in every field, its slope is set by how much structure the particular problem has, and neither of those facts is visible from inside any one of the three vocabularies.

A fourth, which does not fit #

It is worth naming one tolerance that belongs to the same family and is not on the curve, because the reason it is not is instructive.

The stopping tolerance of an iterative solver looks like the others: a constant, compared against a residual, deciding when to stop. It is not a backward error somebody chose, though. Stopping early does not perturb the problem — it returns an approximate answer to the exact problem, which is a forward error, and a small residual is not a small error is the essay about how far apart those can be, and the whole point of the site’s error identity is that those are different positions.

The distinction has a consequence that is easy to state and easy to get wrong. Loosening a drop tolerance changes the preconditioner and not the answer; loosening a stopping tolerance changes the answer and not the problem; loosening a deflation criterion changes the problem. Three constants that a caller meets in the same routine, in the same units, doing three different things to the error identity.

The knee, which is the only thing anybody actually wants #

A trade curve is used by looking for its knee — the place where more error stops buying much work, or more work stops buying much error — and the three curves here have one in the same place for the same reason.

The fourth case has a knee of a different kind, and sweeping it prices the whole question. Where the tolerances above are offers, semiconvergence is a curve with a minimum in it: the error falls, reaches a best value, and then rises without limit.

The best achievable error is almost flat and the penalty for missing it is not. Across noise of 0.001, 0.003, 0.03, 0.05, 0.1 and 0.2 — a factor of two hundred — the best error moves only 0.1050, 0.1146, 0.1523, 0.1562, 0.1675, 0.1918, a factor of 1.8. Over the same range the cost of running to step 120 instead of stopping goes 5.3, 15.8, 118.9, 193.8, 361.5 and 631 times the best.

So two hundred times more noise costs under a factor of two in the answer, provided the stopping step is right — and the step that is right moves from 44 to 2 across the same range. Nearly all of the available accuracy is decided by when to stop rather than by how good the data was, which inverts the intuition that a noisier problem is a worse-answered one.

The rule that is actually used stops too early, consistently, and by a knowable amount. The discrepancy principle halts at steps 27, 16, 4, 3, 3 and 2 against optima of 44, 32, 7, 5, 3 and 2 — short by 39%, 50%, 43% and 40% at the four lower noise levels, and exact at the two highest. It is therefore safe in the direction that matters, since the curve is far steeper to the right of its minimum than to the left, and it is leaving real accuracy on the table on exactly the problems where the most is available.

That asymmetry is the reason the rule survives being wrong by half. Stopping ten steps early on the 0.001 curve costs a few per cent; stopping ten steps late costs a factor. A rule tuned to the midpoint of its own error bar would be worse than one biased low, and the discrepancy principle is biased low by construction rather than by accident.

The three curves look, on the figure, as though they flatten below about 10⁻¹⁰ and steepen above about 10⁻³, with the useful band the four decades in between. That reads as a reassuring result, and it is the one claim in this essay that a picture makes and a number does not support.

Where each curve actually starts buying #

Take the error at which each trade first buys five per cent of its work, and the error at which it reaches half:

                 five per cent      half
deflation          1.1·10⁻¹⁴      1.5·10⁻³
drop               3.5·10⁻⁵       8.1·10⁻³
truncation         6.1·10⁻⁵       6.0·10⁻³

The onsets are nine orders apart. Deflation is not flat below 10⁻¹⁰ at all: it has bought 21% of its iterations at an accepted error of 6.7·10⁻¹³ and 9% at 1.2·10⁻¹⁴, both of which are inside the region the paragraph above calls flat, and roughly two fifths of everything it ever buys is bought below 10⁻¹⁰. The other two are flat well past 10⁻¹⁰ — the drop curve is still at 0.4% of its entries at an accepted error of 3.8·10⁻⁷.

So of the three, none has its onset near 10⁻¹⁰. One is ten thousand times tighter and two are five thousand times looser, and the four-decade band is not a shared feature; it is the range the figure’s axis happens to cover.

The truncation curve has a second problem the band conceals, which the negative-end section above already names: its saving is negative for its first four points and crosses zero only at 6.1·10⁻⁵. Its useful range therefore begins two decades above where the essay’s band ends the flat region, and the part of the curve inside the supposedly-useful band is the part where the factored form costs more than the matrix.

What the three do agree about #

The halfway points: 1.5·10⁻³, 8.1·10⁻³ and 6.0·10⁻³, which sit inside a factor of five of each other. The curves agree about where the work is mostly gone and not about where it starts being bought, and those are different claims with different consequences.

The second is the one a defaults argument needs. If the three onsets were together, a library author in any of the three fields could reason about a tolerance by analogy with another field’s. They are nine orders apart, so nobody can: a deflation criterion at the drop tolerance’s onset would deflate nothing, and a drop tolerance at the deflation criterion’s would store the exact factor. What is shared is the shape — a flat region, a rise, a steep end — and the shape is what the three vocabularies have in common. Where the features sit on the axis is a property of each problem, which is what the differing slopes already said and what the knee claim would have contradicted.

Where the defaults came from #

The three defaults do all sit somewhere on the useful part of their own curve, which is worth asking about even though — per the section above — those parts are not the same band. The answers are unrelated.

The deflation criterion in every implementation descended from the original QR algorithm — whose shifts are never formed either — is a small multiple of the unit roundoff times the sum of two neighbouring diagonal entries. That form has a reason: it makes the perturbation relatively small compared with the local scale, so a deflation does not damage a small eigenvalue in a matrix with a large one. It was chosen to be as tight as it could be while still firing, which puts it at the flat left end of its curve.

The drop tolerance’s usual default of 10⁻³ or 10⁻⁴ came from a different argument entirely: it is what was found, empirically, to produce a factor that fits in memory while still preconditioning usefully. That is a statement about the other axis — the work — and it was tuned by watching iteration counts rather than accuracy.

The truncation rank is usually chosen by a caller from a plot of singular values, by eye, at a visible gap or a visible knee. That is neither axis; it is a judgement about the data.

Three constants arrived at by three arguments — tightness, memory, and a picture — each landing on the part of its own curve where the trade is live rather than in the flat region or past the damage. That is the modest cheerful result at the centre of this essay, and it is smaller than the version that had all three landing in one band: what the three communities got right is each its own curve, independently, and there is no evidence that they got a shared one.

The distinction matters because only the smaller claim is defensible from the measurement. Three defaults on three curves is three separate pieces of good judgement, which is what one would hope for. Three defaults in one band would have been a coincidence worth explaining, and there is no coincidence to explain.

What this is not #

Two things it would be easy to take from the above and should not be.

It is not that the three tolerances are interchangeable. They perturb different objects and the perturbations propagate differently. A deflation criterion’s error enters as a perturbation of the matrix whose eigenvalues are wanted, so it is amplified by the eigenvalue conditioning. A drop tolerance’s error enters as a perturbation of a preconditioner, which affects the rate and not the answer — the iteration converges to the solution of the original system whatever the preconditioner is. A truncation’s error enters as a perturbation of the answer itself, with no amplification at all.

Three positions in the error identity, and only the first of them is amplified by a condition number.

And it is not an argument for tuning them. The flat left end of every curve says that tightening a tolerance below the knee costs work and buys nothing measurable, and the steep right end says loosening it past the knee buys work and costs the answer. The defaults are in the band. The value of the picture is understanding what kind of quantity is being chosen, not choosing it differently.

What the rest of this site does with the same idea #

There is a fourth instance on this site that is not a tolerance and is the same trade, and it is worth finishing on because it makes the shape general rather than particular to a comparison.

Every mixed-precision result in this collection is a point on this curve. Computing a preconditioner at three significand bits rather than fifty-three is accepting a backward error in the preconditioner — a large one — in exchange for work not done. The essays that measured it found the preconditioner roundable to three bits and the residual not roundable at all, which is the same statement as the distinction above: the preconditioner’s error is in the mild position of the error identity and the residual’s is not.

So the general form of what this essay has been about:

Any decision to compute something less exactly than possible is a backward error accepted in exchange for work not done, and it can be plotted. Precision, sparsity, rank, deflation, and the whole of iterative refinement are the same trade in different units, and a code contains dozens of them that were each chosen by somebody looking at one of them alone.

The refusal #

The assertion is fed a drop tolerance of one.

At that value every off-diagonal entry of the incomplete factor is discarded, so LLᵀ is diagonal and the “incomplete factorisation” is a scaling. On the model problem the diagonal is constant, so the preconditioner is a multiple of the identity and buys exactly nothing: the preconditioned iteration takes the same number of steps as the unpreconditioned one.

A trade curve that reported it as an ordinary point would be reporting a preconditioner that does not precondition, at a plausible-looking place on the axis, with a backward error of 0.43 that looks like the honest right-hand end of a sweep. The refusal is what keeps the last point on a curve from being a different kind of object from the rest of it.

What is next #

Every tolerance in this essay is an offer: accept this much error, save this much work, and the trade is monotone in both directions so there is no way to be wrong about it except by choosing a point nobody wanted.

The last essay is about the other kind, where both directions are failures — where the constant does not buy anything, it decides which of several true answers the computation returns, and at a low enough precision it produces a proof of something false from a comparison that was performed correctly.