Unit roundoff — where it appears
Named by 53 essays across 14 fields — each of them below, with the objects they name alongside it.
The same program, twice
One vector of 4,096 numbers, one summation algorithm, one precision, twenty-six runs — and twenty-one different answers. Nothing in the program chose between them, every one of them satisfies the textbook bound, and the exactly rounded answer is not among them.
What a float can hold
The representable numbers are not a fine fuzz spread evenly over the line. They are evenly spaced inside each power-of-two interval and twice as far apart in the next one up, and almost everything else in this subject is a consequence of that one fact.
Four 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.
A bound every answer satisfies
The classical bound on a summation error is correct, it covers all twenty-six answers one vector produced, and it is 7,932 times larger than the difference between them. A statement true of every ordering cannot say which ordering you got.
The part of a solver that may be rounded
A preconditioner computed and applied with a three-bit significand still returns thirteen correct digits — it costs seventeen extra iterations and nothing else. Round the working arithmetic instead and the step count barely moves while the answer loses exactly the digits the format dropped.
The product nobody had to form
The Hankel singular values are the square roots of the eigenvalues of PQ. Form that product and half of them stop existing, at a floor one number predicts — and the fix is the one the least-squares field has had since its first essay, arriving in a place with no least-squares problem in it.
Where the disagreement comes from
The error of a reduction is a walk whose step length is the spacing of the running total, not of the answer. That one sentence predicts the size of the disagreement to a factor of two, explains why dividing the work makes it smaller, and explains why the value cannot be predicted at all.
Doing 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.
The sum that cannot be wrong
Snap every addend to a common multiple before adding, and every partial sum is exact — so the order stops mattering, by construction rather than by luck. Four hundred permutations return one value where an ordinary reduction returns three hundred and three.
A factorisation with nothing to pivot for
Cholesky's growth factor is not bounded by one. It is equal to one, at every size and every condition number, and the two-line reason is why the algorithm needs no pivoting at all — not "usually gets away without it". Its only failure is the square root of a non-positive number, which is exactly the test for definiteness, and in floating point that test moves with the precision.
Where 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.
The other half of a format
fp16 and tf32 have the same eleven significand bits and their largest numbers are 65,504 and 3.4·10³⁸. For two phases this site simulated the significand alone, so it was obliged to report them as the same format — which is a claim, and a false one.
The sketch that is spent
Every other object a sequence carries has a shelf life. A random sketch has one use. Deflate what its first round found and apply it again, and it returns the zero matrix — 9.0·10⁻¹⁵ where the first round saw 2.62 — because the input has been made orthogonal to the very draw the guarantee is over.
A rule that is correct and unusable
Cramer's rule gives every component of the solution in closed form, in terms of determinants, and it is a theorem. On two-by-two systems whose rows are nearly parallel it returns an answer with a backward error of 458 units of roundoff where elimination returns 1.3 — on a matrix whose condition number is 32,000 and which elimination solved perfectly.
Eight bits, and a format that breaks the rules
E4M3 reuses the exponent code IEEE reserves for infinities, so it reaches 448 where the same bits under IEEE's rules would reach 240 — and has no infinity left to signal an overflow with. The same computation is a NaN on one conforming device and 448 on another.
The gap refinement can close
Multiplying by a computed inverse is not backward stable, and refinement at the working precision repairs it. That much is settled. The claim beside it — that the forward error does not move — was read at one conditioning and four corrections too late. Swept over ten, it moves at every one, and it lands on the LU route's own number after a single correction.
The direction the error leans
The size of one rounding error is set by the precision. How ten thousand of them combine is set by something else entirely — the rounding mode — and the fitted exponents are 0.47 for round-to-nearest and 1.01 for round-toward-infinity, on identical data at identical precision.
A coin flip that fixes the average
Add 0.1 to 256 a thousand times at eight significand bits and the answer is 256. Not approximately — the total never moves, not once, and no error bound says so. Round up one time in twenty instead of never, and it arrives at 348 against a true 356.
A condition number that is not the model's
κ(P)κ(Q) is quoted as the reason one route to the Hankel singular values fails, and it is. It is also read as a measure of how reducible a model is, and it is not — the norm of the Gramian does not move at all as the McMillan degree runs from four to fourteen, and the condition number wanders over a factor of thirty-five with no trend.
One minus a leverage is a subtraction
Every deletion diagnostic divides by 1 − h, and computing it as one minus a computed leverage loses digits in proportion to 1/(1 − h), however accurate the leverage. The complementary block of a QR factor gives the same number as a sum of squares and loses κ(A)·u instead: every digit on a well-conditioned design, and half the digits the subtraction loses on a design whose far point is what made 1 − h small.
A relation among digits that were not there
A lattice finds the exact integer combination of several numbers that vanishes, and it needs enough digits of them to do it. Give it more digits than the numbers have and it finds a relation anyway — among the rounding, with the same confidence and no warning. Recovery runs 8 of 8 at twelve digits and 1 of 8 at forty.
The tolerance that buys no agreement
Ask for four more orders of accuracy and you get them — the answers improve by a factor of 1.5 million. The ratio between the best and the worst run is 1.34, 1.48, 1.71 and 1.17 across the same sweep. The band falls and it does not close.
The knob and the rounding
The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect. The one rounding nobody writes down decides everything: above 2⁵³ the reduction returns a basis 12,345 times worse than it should, with the determinant invariant equal to one throughout.
One number that has to be right
Householder's orthogonality was called structural: a reflection is built from a unit vector, so rounding the vector names a different reflection rather than a broken one. Tested by breaking it, the claim is narrower and sharper. Perturb every component of the reflector by a relative 10⁻², and ‖QᵀQ − I‖ stays at 1.5·10⁻¹⁵ while the factorisation moves to 5·10⁻³. Perturb the one stored scalar by the same amount and ‖QᵀQ − I‖ is 6.5·10⁻². The structure is one degree of freedom, and the departure is four times its relative error.
A bound that is proved
Every error statement in the essays before this one is a measurement of one run. Interval arithmetic makes a different kind of claim — the answer lies in this set, for this input, with no probability attached — and its failure mode is that it returns nothing at all. On a Hilbert system it proves a bound 23 times the error it bounds, and one size later it refuses.
A triangle where the scalar was
Every level-3 QR assembles a block of reflectors into Q = I − Y T Yᵀ, and T is computed by a recurrence whose inputs are its own previous columns. A block of sixteen carries 136 computed numbers where sixteen separate reflections carry sixteen. The orthogonality it produces is 3.9·10⁻¹⁵ against the single reflector's 7.8·10⁻¹⁶ — a factor of five for a hundred and thirty-six times as many things that have to be right.
Proving the answer is in the box
Every other method here computes a number and estimates how wrong it is. This one returns a verdict: there is exactly one solution in this box, or there is none, or — the honest third outcome — nothing can be said. Two of the three are proofs about infinitely many points from finitely many operations.
Three errors and one number
This site's identity has two factors and a division of blame between them. Two fields have now added a third party and a fourth, and only one of the four is a property of anything — the others are decisions, made before the arithmetic, reported by nothing.
The factor a sparse code keeps anyway
Every deletion diagnostic divides by one minus a leverage, and computing it as a subtraction loses a digit for every decade the leverage is from one. The route that does not subtract needs the orthogonal factor, which a sparse factorisation is supposed not to have. Three repairs that avoid it all fail at exactly a unit of roundoff over the divisor — and the fourth, which reaches the orthogonal factor through the Householder vectors a sparse code keeps in order to solve anything at all, returns the same bits as a stored factor in 900 operations.
Three walks and one bound
A left-to-right sum, a chain of three thousand rotations and a conjugate gradient residual recurrence share no arithmetic and no vocabulary. Each has a standard bound that is linear in whatever it accumulates against. All three come out at a half — 0.486, 0.554 and 0.507 — and nothing is rescaled.
The weight the factor met first
The route to one minus a leverage through the orthogonal factor was said to lose a digit for every decade of the condition number, whatever else it does. Put a weight on one row and it does not. With the heavy row first, the complement keeps every digit at κ(A) = 2.5·10⁹ while both subtractions return nothing. With the same row last it loses digits as the row's scale grows. And two heavy rows that leave κ(A) at 3.1 still lose six digits when the light rows come first. The law was about the order the factor met the rows, and the condition number had been standing in for it.
The residual the solution cannot hold
Sorting a weighted fit's rows heaviest first gave every digit of one minus the heavy row's leverage back. It gives nothing back to the heavy row's residual, if that residual is computed the way every textbook computes it — as the datum minus the fitted value. The fitted value is a double, and a double cannot resolve a misfit smaller than its own last digit times the weight: at a weight of 4²⁴ the residual formed from the solution is wrong in its second digit in every order, and forming the subtraction exactly changes nothing. Taken from the same orthogonal factor as the divisor, the residual keeps fifteen digits, and so does Cook's distance at 3.4·10¹⁷.
Eight blocks and sixty-four reflections
One block of sixteen reflectors, assembled as I − Y T Yᵀ, departed from orthogonality five times as far as a single reflection, and the question was whether a factorisation of many blocks multiplies that factor. It does not. On 96 × 64 matrices eight blocks of eight end at 1.42·10⁻¹⁴ — within a fifth of the root-sum-square of their own departures, and less than half their sum — while the same factorisation taken one reflector at a time ends at 2.91·10⁻¹⁴. A block departs more than a reflector, and there are an eighth as many of them. And a nearly dependent column that swells the triangle's entries to 10²⁶ costs the product nothing.
One sequence and two recurrences
CGLS and LSQR compute the same iterates — the minimiser over a space is unique, so there is nothing to choose between them in the algebra. At κ = 10⁶ they cost 42 steps and 47. At κ = 10¹⁰ they cost 110 and 209, across four seeds, and the quantity that separates them is the orthogonality of a basis neither of them keeps.
The licence is not the boundary
Cholesky QR is licensed by κ²u ≪ 1, which reaches equality at κ = 9.5·10⁷ in double precision. At 10⁸ the factor it returns is already 0.37 away from orthogonal, and it goes on returning factors as far as 10¹³ — refusing at scattered condition numbers in between, at different ones for eight columns and for six.
Nine steps of pessimism
A proved bound is 8 to 26 times the error it bounds, at every precision from 16 to 40 significand bits. A carried interval is (√2)ᵐ times too wide after m re-enclosures. The two cross between eight and nine, so the method everybody warns against is the tighter of the two for a short computation.
A multiplier is a force
A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.
The reading that never moves
Across thirty runs — five grids from 36 to 196 unknowns, six working precisions from 53 significand bits down to 8 — the residual conjugate gradients stops on stays between 1.10·10⁻¹³ and 9.95·10⁻¹³. Over the same thirty runs the error of the answer spans a factor of 2.39·10¹¹, and the step count more than doubles. The one number the run publishes is the only one that responds to neither axis.
The far well in a byte
Half precision's subnormals carried a two-well chain's far well ten octaves deeper than flush to zero, and the essay that measured it predicted that on the eight-bit formats the band would be worth almost nothing and starting high almost everything. Measured on nine chains, the band is worth what it always was, two or three octaves; starting at the top of the range is worth ten and fourteen; and at three significant bits the far well is lost on eight chains of nine with no exponent limit at all, because the precision fails before the range does.
The honest residual is not a stopping test
A conjugate-gradient run in reduced working precision reports a residual pinned near 10⁻¹² while its error spans eleven orders, and the repair was to recompute the residual in double. As a report it works: on thirty runs it lands within a factor of a quarter to five of the error. As the thing to stop on it fails outright: below 53 bits it is passed on none of twenty-five runs, which go on to the 300-step cap or until their own recurrence collapses — 7,694 products in all against 605. One clause fixes it. Stop also when two checks in a row fail to halve the double residual, and every run ends within thirty-six products, at the same error, reporting a number that means something — and at 8 and 11 bits on the larger grids, sooner than the recurrence's own test.
The formula sets the power, the sum sets the constant
The one-pass variance was found losing three to sixty-nine times more than the digits-lost rule allows, and the explanation offered — operands built from a thousand roundings — was never priced. Measured against the exact variance of the stored data, the rule's ratio is the variance's own condition number squared, and the formula decides what power of it the error grows with: two for every one-pass variant, one for Welford's update, none for two passes or a shift. The summation decides only the constant in front — about 0.4√n for running sums, one for pairwise or compensated ones — and the sixty-nine was neither: it belonged to the random numbers.
A floor the error has not reached
The residual a reduced-precision conjugate-gradient run stops on, recomputed in double, has a floor, and the floor can be predicted: on sixty runs of three problems it sits within a factor of 3.3 of a constant times u·‖|A||x|‖/‖b‖. The prediction was that the unit roundoff and the grid would be enough. They are not — adding the grid's size or κ(A) makes the prediction worse than u alone — and the quantity that works reads the solution. Nor is the floor a signal to stop. When the residual first comes within four times its own floor, the error is still a median 4.6 to 12.6 times its least, and on the slowest problem the least error arrives a median 76 steps later. A clause that stops there stops some run of every problem at three times its least error or more. What the floor can do is tell a run when to start checking often: switching to five-step checks within four times it keeps the error within a tenth of its least on both Laplacian problems and cuts the rate-set clause's overrun from 1,661 steps to 198.
The generator that rounded its own product
A one-pass variance leaned the same way on forty-one seeds, and the low bits of a congruential generator were the suspect. Replacing the lowest five bits made the lean larger, not smaller. The generator was not congruential at all: written in double precision, its product of two 31-bit numbers was rounded before the modulus, its states collapsed onto a handful of low bytes, and those are the bits a running sum near a billion throws away. The exact recurrence does not lean, and random bits are not neutral either: fewer of them than the sum discards all round one way.
The sum can be single, the residual cannot
A sliding least-squares window's correction has to read every row, so the cheaper correction proposed instead was one whose residual is formed in single precision and summed in double. It was predicted to cost little at κ(A) = 3·10⁴ and a great deal at 3·10⁶. It costs seven to eight decades at both: the window ends at 3.7·10⁻² instead of 3.3·10⁻⁹ at the worse conditioning and at 3.1·10⁻⁴ instead of 2.2·10⁻¹² at the better. The single residual's error is a fixed fraction of single precision's unit roundoff times κ(A), at every noise level, because its rounding reaches the answer through the rows themselves and is amplified once, not squared. The other half of the correction behaves the other way: summing the rows weighted by a double residual in single is free when the data fit exactly and costs in proportion to the residual otherwise, two decades for every decade of κ.
A later look is a worse stop
Every stopping test for reduced-precision conjugate gradients had read the residual, and the residual flattens tens of steps before the error stops falling. The method carries a cheap lower bound on its own energy error — the sum of each step's step length times its squared residual over a window of steps that follow — and a clause that stops when that bound falls below the working precision's share of the iterate stops twenty runs on the scaled Laplacian within 1.22 times their least error, a third of the residual clause's overrun. The prediction that it would stop within thirty steps of the least on the median run misses by three. And the window turns out to be a pure delay: in reduced precision the error creeps back up after its least, so the longer the window waits, the worse the stop.
A short window from the start
Conjugate gradients carries a cheap lower bound on its own energy error, summed over a window of later steps, and a clause that stops when it falls below the working precision is safe — but the window is a pure delay. A window that starts at twenty and halves each time the estimate falls by a decade was predicted to keep the long window's safety and lose most of its delay. It loses the delay: under half window 20's overrun. It does not stop every run within 1.12 of its least error, as predicted; its worst is 1.126. And a plain window of five, which never needed to shrink, beats it on both counts at once — 1.097 at worst, 239 steps past the least in all against 335. The thing the shrinking was meant to avoid, stopping before the least, costs at most a few per cent, because near its least the error is flat.
The plateau is set by the length
A Householder factor applied through its reflectors, never formed, loses orthogonality over its first twenty or so reflectors and then stops. The saturation was predicted to be a property of the vector length: on 384-long vectors the growth should continue longer before it stops. It does not. On 96-, 192- and 384-long vectors the departure reaches nine-tenths of its plateau within twenty reflectors, and on the longest it gets there soonest. What the length sets is the plateau itself — 3.6, 5.0 and 6.7·10⁻¹⁵ — which is the unit roundoff times the square root of the length, times a constant between 3.1 and 3.4. Twice the reflectors on the same length move it by nine per cent.
The residual the method reports
Conjugate gradients prints a relative residual of 6.9·10⁻²¹. The unit roundoff is 1.1·10⁻¹⁶, so that is not a small residual and not a large one — it is not a residual. The vector the method is holding at that step has ‖b − Ax‖/‖b‖ = 5.1·10⁻¹⁰, and nothing in the run says so.
Every trip comes back shorter
An applied Householder factor stops losing orthogonality after about twenty reflectors, at a height that grows like the square root of the vectors' length, because rounding to nearest makes errors of random sign. Rounding every operation toward zero makes errors of one sign, and the plateau was predicted to grow like the length itself — doubling for each doubling. In single precision it does nothing of the kind: from 96 rows to 768, eight times the length, the departure after 64 reflectors grows by a factor of 1.6. An inner product does pile up its errors toward zero, a third of a unit a term, but only when its terms share a sign; Householder's inner products do not, and theirs grow like the square root as before. What rounding toward zero adds is something nearest never does: every vector sent through the factor and back comes home about a unit shorter per reflector, at every length. That shrink is a floor under the departure and has no plateau; rescaling every reflection to its input's length removes it and leaves the departure still climbing.
A bound on the fall, not the error
A five-step window in Hestenes and Stiefel's error clause stopped forty steady conjugate-gradient runs promptly and safely, and was predicted to stay safe through a stall, because a lower bound on the error should sit just below an error that is sitting still. On twenty runs that stall because rounding has made them repeat themselves, it does: the bound stays above half the error on every stalled step and window 5 stops within 1.12 of the least. On runs that stall in exact arithmetic — one eigenvalue far below the other forty-seven, carrying a share of the energy — it stops more than half again too high on six runs of twenty-four, and on two at nine and ten times the least. The window sum is the energy the error lost over the window, which is a lower bound only because what is left is not negative. On a stall the loss is the other eigenvalues' remainder; it falls geometrically while the error waits, by a factor of about the square root of the isolated eigenvalue, and at low precision it crosses the threshold first.
A threshold the matrix does not set
Two numbers come out of a relative-accuracy comparison and they belong to different things. The size of the matrix moves the constant of the routes that never fail, by a factor of 2.7 between n = 4 and n = 10; it does not move the point where the route through BᵀB stops returning an answer, which sits between ten and eleven decades of grading at every size drawn.
The error the method already knows
Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.
A walk needs a length
The gap between the two residuals grows as the square root of something, and a square root needs a length. Two quantities are candidates — how far the iterates travelled and how many steps were taken — and only a second sweep separates them. Across a fourfold change in size the iteration count goes from 39 to 96 and the gap goes from 5.04·10⁻¹⁵ to 5.33·10⁻¹⁵.
Named alongside it
The objects these essays reach for when they reach for this one.
Condition numberResidualConjugate gradientsBackward errorCatastrophic cancellationError accumulationExact ground truthForward errorHouseholder reflectionQR factorisationStopping criterionMixed-precision