Deciding that a zero has arrived

The three tolerances of the previous essay were offers. Accept this much error, save this much work; the curve is monotone in both directions, and the only way to be wrong about it is to choose a point nobody wanted.

A detection threshold is a different object, and the difference is not a matter of degree. Both of its directions are failures.

Declare a zero too early and an answer that was available is thrown away. Declare it too late and the next step divides by rounding error. There is no trade because there is nothing being bought — the constant is not purchasing work, it is deciding what the computation concludes, which is the difference between a zero somebody is allowed to write and one somebody has to detect.

One matrix, three answers #

Start with the least alarming version. Build a symmetric matrix whose spectrum has three coarse clusters of width 10⁻⁴, each split into three finer ones of width 10⁻¹⁰. The matrix genuinely has a near-invariant subspace of dimension three, another of dimension nine, and an exactly invariant one of dimension twenty-seven. All three are real.

Run an Arnoldi recurrence and vary only the constant it compares its subdiagonal against.

It stops at step 3 at the loose end, leaving a relative residual of 1.5·10⁻⁵. It stops at step 9 in the middle, leaving 2.7·10⁻¹⁶. It stops at step 27 at the tight end, leaving 5.5·10⁻¹⁷.

None of those is wrong. Each is the recurrence correctly detecting one of the invariant structures the matrix has, and which one it detects is a property of the constant rather than of the matrix.

The two ends are the two failures, and they are worth naming as failures rather than as choices.

Too loose is an answer thrown away. Stopping at step 3 leaves a residual of 10⁻⁵ that the next six steps would have removed, on a problem where twenty-four steps remain available. The method has finished with 10⁻⁵ of the answer missing and reported success.

Too tight is a division by rounding — an eigenvalue that arrives twice is what the steps after it produce. Past the point where the subdiagonal has fallen to the roundoff, the recurrence is normalising a vector that is entirely orthogonalisation error, and the “basis vector” it produces points in a direction determined by the arithmetic. Every subsequent step builds on it.

Sweeping the width across six decades separates two things that a single picture cannot.

The stops do not move and the residual does, and that division is the point of the figure. Where the recurrence stops is decided by the spectrum, which the threshold cannot touch; the accuracy it reports at those stops scales with the threshold almost exactly.

The stopping points do not move at all and the residual moves exactly with the tolerance. Across widths of 10⁻², 10⁻³, 10⁻⁵, 10⁻⁶ and 10⁻⁷ the recurrence stops at 27, 9 and 3 every single time, on the same three subspaces — while the largest residual runs 1.52·10⁻³, 1.51·10⁻⁴, 1.51·10⁻⁶, 1.51·10⁻⁷, 1.51·10⁻⁸. That is 0.151 η at every stop, to three digits.

The constant is stable enough to quote: the largest residual is 0.151 η at 10⁻³, at 10⁻⁶, and at every stop between. So the threshold buys accuracy one for one and buys no change at all in where the recurrence chooses to stop.

So the constant buys accuracy and decides nothing structural — until it does, discontinuously. Six decades of tolerance move the answer’s residual by six decades and move the decision not at all: the same three clusters are found, at the same three dimensions, every time. That is the reassuring reading and it is the reading the essay’s opening figure refutes, because the staircase’s first two steps do eventually merge, and when they do the count changes by a whole eigenvalue rather than by a proportional amount. A parameter that is perfectly linear in its effect over six decades and then jumps by an integer is the hardest kind to choose, because every experiment a careful caller runs inside the linear range confirms that the choice does not matter.

It also says what a sensitivity study can and cannot establish here. The standard defence against a typed constant is to vary it and check the answer is stable, and on this matrix that defence returns a clean bill at every width from 10⁻² to 10⁻⁷: three stops, three dimensions, a residual that scales as it should. The study is correctly performed and its conclusion — the tolerance does not decide anything — is true throughout the range examined and false immediately outside it. What would have to be varied is not the tolerance but the matrix, because the discontinuity lives in the spacing of the spectrum rather than in the constant: it is the coarse width closing on the fine one that merges the steps, and no amount of moving η explores that. So the honest form of the check is to perturb the problem and watch the count, which costs a second factorisation and is the only version that can fail. Varying the constant alone measures the flat part of a function whose interesting behaviour is a step, and reports the flatness.

A count that a constant moves by whole eigenvalues #

The second instance is worse, because the quantity it decides is an integer.

The number of infinite eigenvalues of a pencil is n minus the degree of its characteristic polynomial, and on exact data that is a fact. On float data it is the number of singular values of B judged to be zero — a rank decision, and this collection has an essay saying at length that a rank is a decision.

Sweeping the tolerance on one perturbed descriptor pencil whose true count is two:

τ = 10⁻¹⁶ … 10⁻¹² count 0 τ = 10⁻¹⁰ count 1 τ = 10⁻⁸ … 10⁻² count 2 τ = 10⁻¹ count 3 τ = 3·10⁻¹ count 4

One matrix, five different answers, and the differences are not digits. A pencil judged to have two infinite eigenvalues when it has three has one spurious finite eigenvalue in its output, at a value that is the ratio of two quantities which are both rounding error — and there is nothing about its residual that says so, because a small residual is not a small error and one is available for it.

There is a band of tolerances that gets it right, and it is wide — six decades. That is the ordinary case and it is why this works most of the time. What the sweep shows is that the width of the band is a property of the matrix, that nothing in the output reports how close to an edge of it the chosen τ was, and that the failure at each edge is silent.

Why the band is not a safety margin #

There is a tempting reading of the pencil sweep above — six decades of tolerance give the right answer, so the decision is robust — and it is worth taking apart, because it is the reading that makes this kind of failure surprising when it arrives.

The width of the band is set by the gap in the singular values of B: it runs from the size of the perturbation up to the smallest genuine singular value. Both ends are properties of the problem. On the constructed pencil here the gap is eight orders wide and the band is comfortable; on a pencil assembled from measured data it is whatever the measurement noise and the model leave, and it can be nothing at all.

What makes it dangerous is that the width is not reported. A routine given τ = 10⁻⁸ returns a count, and returns exactly the same count in the comfortable case and in the case where τ was a factor of two from the edge. The number that says which — the ratio of the largest singular value below the cut to the smallest above it — is computed on the way to the answer and discarded.

That is the same complaint as the previous essays’ and it is the reason this collection’s own rank machinery returns a gap and a verdict rather than a verdict.

And a proof of something false #

The third instance is the one worth the essay’s title.

Conjugate gradients decides a matrix is indefinite by testing the sign of pᵀAp. That is not a tolerance at all — the constant is zero, the comparison is exact, and there is no judgement in it. It is the cleanest possible detection: a sign.

A sign of a computed quantity is unreliable when the quantity is smaller than its own rounding error. pᵀAp/pᵀp is a Rayleigh quotient, so it is bounded below by λ_min; the rounding in the inner product is about u·‖A‖. So the sign means nothing once λ_min/λ_max falls below roughly u·n — the boundary eight bits and a format that breaks the rules meets from the format’s side — and past that point, a positive definite matrix produces a direction that certifies it is not.

The hero is that region. Every matrix in it has spectrum κ^(−i/(n−1)), so its smallest eigenvalue is 1/κ and none of them is negative. The filled cells are runs where the iteration produced a certificate, and the number in each is the step at which it did.

The boundary sits at twelve significand bits. At fourteen and above, over eight decades of conditioning, the test is never wrong. At twelve and below it is wrong somewhere, and at eight it is wrong from κ = 10⁵ — which is not an extreme condition number by any standard.

How the region moves with the size, which is not how it should #

The natural reading is that a shorter iteration gives the rounding fewer chances, so the region should shrink as n falls. Counting filled cells over the same grid — nine significand widths against eight condition numbers, seventy-two cells:

   n      filled cells    clean from
   8          30          never, up to 16 bits
  16          20          14 bits
  30          15          14 bits
  48          18          13 bits
  64          21          13 bits

The region is largest at the smallest n. At eight unknowns the test is wrong somewhere at every width tried up to sixteen bits, where at thirty it is clean from fourteen. And the count is not monotone in the other direction either: it falls to fifteen at n = 30 and rises again to twenty-one at sixty-four, so the smallest region is in the middle of the range rather than at an end.

The bits required move the same way. Fourteen at n = 16 and 30, thirteen at 48 and 64 — falling as the problem grows, where a u·n criterion would have them rise. So whatever governs the boundary is not the number of inner products a step performs.

What it looks like instead is a competition between two effects. A larger n gives more steps for the rounding to accumulate over, which is the “more chances” reading and pushes the region up. It also gives the Krylov space more directions to resolve the same condition number with, so each search direction is a smaller correction and the quotient pᵀAp/pᵀp stays further from the rounding — which pushes it down. The two balance near n = 30 on this family, and neither is available from the u·n argument.

The essay’s headline is unaffected, and it is worth being clear which claim survives: at n = 30 the boundary is at twelve bits and fourteen is clean over eight decades, exactly as measured. What does not survive is the extrapolation to other sizes, in either direction.

That is worth one more sentence because it is the general hazard of a two-dimensional figure. The hero sweeps bits against conditioning at one size, and the size is a third axis the picture cannot show — so a reader takes the picture as being about bits and conditioning, and the caption on the second figure quietly makes a claim about the third. A figure with a slider has as many axes as the slider plus two, and the ones off the picture are the ones a caption is most likely to be wrong about, because nothing draws them.

Twelve bits is not an exotic place to be #

Eight significand bits is the E4M3 format that this collection has an essay about, and half the hardware sold for numerical work now implements it. Eleven is half precision. Twelve is between them.

None of this is a warning about a museum piece. It is a statement that the arithmetic the field is moving towards has a unit roundoff at which a test everybody treats as exact stops being exact, and that the failure mode is a proof rather than a wrong number.

The mechanism, in one line #

It is worth writing out why twelve rather than sixteen or eight, because the boundary is not arbitrary and the argument gives a rule.

The quotient being tested is q = pᵀAp/pᵀp, whose true value is at least λ_min. The rounding in a dot product of length n is about n·u·‖p‖‖Ap‖, and ‖Ap‖ ≤ λ_max‖p‖, so the computed q is q plus something of size n·u·λ_max. The sign is unreliable once

λ_min ⁄ λ_max < n · u

which is 1/κ < n·u, or κ > 1/(n·u).

At fifty-three bits and n = 30 that is κ > 5·10¹⁴. At twenty-four bits, κ > 2·10⁶. At eight bits, κ > 1.7·10². The measured boundary is looser than that at every precision, because the conjugate gradient directions do not reach the smallest eigenvalue immediately and a shorter run never gets near it — which is the same effect that made the certificate hard to find in the essay on negative curvature, arriving here as protection rather than as cost.

The rule that falls out is worth carrying: a sign test on a Rayleigh quotient is trustworthy when κ·n·u is well below one, and is a coin flip when it is not. It costs nothing to check and it is not checked anywhere.

What is actually being decided #

Put the three instances beside each other and the shape they share is clear.

In each of them, a quantity is compared against a constant and the conclusion changes. Not the accuracy — the conclusion. A recurrence stops at three or at nine or at twenty-seven; a pencil has one or two or four infinite eigenvalues; a matrix is positive definite or it is not.

Those are discrete outcomes reached by comparing a continuous quantity against a constant, which is the definition of a decision. And a decision has a property that a trade does not: it can be wrong, and the wrongness is not measured in digits.

That is the whole difference from the previous essay. A tolerance that buys work costs accuracy in proportion, so a bad choice is a suboptimal point on a curve. A tolerance that decides costs a conclusion, so a bad choice is a different answer to a question with only one right one.

What can be done about them #

Three things, in increasing order of how rarely they are done.

Report which side of the decision was close. Every one of these thresholds has a quantity beside it, and the ratio of that quantity to the threshold is a free measure of how confident the decision was. A rank decision backed by a gap of 10¹⁴ and one backed by a gap of 3 are different objects; this collection’s own rank machinery returns the gap alongside the count for exactly that reason, and almost nothing else does.

Report what the decision was about. A breakdown detected at step k should say whether the vectors were small or the inner product was — which the previous essays in this run showed is the difference between finishing and failing, costs two norms, and cannot be recovered afterwards.

And verify a conclusion in the precision the claim is made in. A certificate of negative curvature costs one matrix–vector product to check from outside, and the check is independent of the iteration that produced it. At eight bits it is the only thing standing between a proof and a rounding error.

A fourth threshold, which this essay’s own machinery contains #

Every essay in this run is drawn by a generator, and several of those generators contain a threshold of exactly the kind being described. It is worth admitting one.

The Arnoldi recurrence in this collection’s own library declares a breakdown when the subdiagonal is below 10⁻¹⁰ times the Frobenius norm of the matrix. That constant was not derived. It was raised from 10⁻¹³ while these figures were being drawn, because at 10⁻¹³ a spectrum with twelve distinct eigenvalues did not break down at all — the measured subdiagonal there is 5·10⁻¹², which is above the threshold — and the figure that was meant to show the recurrence stopping at twelve showed it running past.

The value it was raised to is nine orders below the smallest genuine subdiagonal in any of the spectra drawn, so the band is wide and the choice is safe. It is still a choice, it is still a constant somebody typed, and the essay it enables is about exactly that.

Recording it here rather than in a comment is the point. A tolerance defended in the prose of the argument it supports is a tolerance a reader can disagree with; one buried in a source file is a number nobody will ever look at again.

The refusal #

The assertion is fed the claim that a false certificate appears at double precision.

It is the refusal that keeps the finding honest in the flattering direction. Everything above says the curvature test can be wrong; a routine that reported it wrong at fifty-three significand bits over this range of conditioning would be over-stating the result, and the whole point of drawing a boundary is that there is something on the other side of it.

Over the three conditionings tested at double precision — 10⁶, 10⁸ and 10¹⁰ — there is not one false certificate. The boundary is where the grid says it is, and the assertion fails if the machinery ever starts finding one there.

Where this run of essays ends #

Twelve essays, and one sentence underneath them.

A quantity going to zero is one arithmetic event with two opposite meanings — an object was found, or an object was lost — and nothing in the number says which. An Arnoldi subdiagonal of 10⁻¹⁴ is the answer arriving; a two-sided divisor of 10⁻¹⁴ is a method with nowhere to go. A determinant that is identically zero is a question with no content; a determinant that has merely lost degree is a model with constraints in it. A curvature that changes sign is the most useful object an iteration can produce, or a rounding error wearing a proof’s clothes, and which of those it is depends on the significand width.

The last two essays are the reason the sentence is about programs rather than about mathematics. In floating point no quantity ever is zero, so every one of those events is somebody’s comparison against a constant — and the constant decides which of the two meanings the computation acts on.