Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Summation — where it appears

Adding a list of numbers, which is the smallest computation with an ordering in it. Left to right, smallest first and compensated all give different answers, and how the error grows with the length is a measurement rather than a bound.

Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.

110¹10⁻¹¹10⁻⁸10⁻⁵pieces the vector was divided intodistance from the exact sum, relativethe published boundκ · uone vector, one algorithmdistinct answers21runs26spread, in ulps2.3·10⁷κ of the sum10⁸bound ÷ worst error2.6·10⁴nobody chose pand no answer is the answer

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.

machine · Reduction order κ of the suma component of b − Ax1.01·10¹⁷ad − bc, near-degenerate3.6·10¹⁶qᵢᵀqⱼ, an orthogonality check7.39·10¹⁵pᵀAp, a curvature409zᵀAz, a trace probe41.8rᵀr, a residual norm1measured, not assumedhighest10¹⁷lowest1above 10¹⁰3terms64sums of squares are safeand nobody decides anything from one

The vector that hides it

Every quick demonstration of a parallel sum uses positive numbers, and positive numbers are the one family where the effect is absent. Measured on six inner products this site already computes, the summation condition number runs from exactly 1 to 10¹⁷ — and the safe end is where nobody makes a decision.

machine · Summation 10²10³10⁴10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴terms summedrelative error+∞, −∞ 1.01zero 1.00stochastic 0.50nearest 0.47√n against n, fittednearest, fitted exponent0.47stochastic, fitted exponent0.5toward +∞, fitted exponent1twelve seeds averaged at each sizethe slope is the bias, not the precision

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.

arithmetic · Rounding 02505007501000250275300325350375additionsrunning totalround to nearest: nothing arrivesexactstochasticnearesta thousand additionshalf an ulp at 2561moves, round to nearest0moves, stochastic46relative error, nearest0.28relative error, stochastic0.0228 significand bits, unbounded exponenta flat line is not a small error

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.

arithmetic · Rounding 110¹10²10³110¹10²10³the accumulating quantity, relative to its first valuethe error, relative to its first valuethe bounds: slope 1what all three do: slope ½three mechanisms, one exponenta left-to-right sum0.49a chain of rotations0.55a residual recurrence0.51every bound's slope1spread of the three0.067a bound is a sum of the roundingsand the roundings have signs

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.

arithmetic · Summation 0510152025303540first barrier depth at which the far well is wrong by half, octavesfp16the band adds 11 octaves · starting at the top adds 15E4M3the band adds 2 octaves · starting at the top adds 10E5M2the band adds 3 octaves · starting at the top adds 14flush to zero13gradual underflow24flush, started at the top29gradual, started at the top39flush to zero5gradual underflow7flush, started at the top13gradual, started at the top17flush to zero13gradual underflow16flush, started at the top27gradual, started at the top30dot: median of nine chains · bar: their rangethe headroom is worth more than the band

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.

arithmetic · Subnormals

Named alongside it

The objects these essays reach for when they reach for this one.

Unit roundoffError accumulationReduction orderRounding modesStagnationSummation condition numberAssociativityBackward errorCancellationCatastrophic cancellationCompensated summationConjugate gradients

All concepts