Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Overflow — where it appears

The production of a number too large for the format to represent. It turns a computation into infinities rather than into a wrong answer, which is the good failure mode, and a norm computed naively overflows long before its result would.

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

10¹10²10³10⁴10⁵10⁶10⁷10⁸10⁹10¹⁰110⁴10⁸10¹²10¹⁶condition number κ(A)× short of a double solvebf16fp16fp32bf16fp16fp32the reference is soundreference solve, worst backward error10⁻¹⁶bfloat16 threshold κ256fp32 threshold κ1.7·10⁷eight refinement steps, residual always in doubleflat at 1 means it reached double

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.

arithmetic · Mixed-precision 3456789101100.250.50.751bits in the exponent fieldeach curve as a fraction of its own maximumbfloat16fp16rangeprecisionto 617 decadesto 3.9 digitswhat the split buysbfloat16: largest number3.4·10³⁸fp16: largest number6.6·10⁴a bit of exponent doubles the rangea bit of significand adds a third of a digit

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.

arithmetic · Floating-point -47-37-27-17-7313233301234log₁₀ of the vector's normfp1611 bitsbfloat168 bitstf3211 bitsbinary3224 bitspale: the format's range · blue: √(Σ(xᵢ/m)²)·m · red: √(Σxᵢ²)fp16 and tf32 have the same eleven significand bitsand their bars do not overlap

A norm that overflows before it is a norm

The vector of sixteen thousands has a Euclidean norm of 4,000, which fp16 represents exactly. Written as the square root of the sum of squares it returns infinity, because squaring doubles the exponent — and the expression costs half the format's range on the one computation every iterative method performs at every step.

arithmetic · Overflow 10⁻⁷10⁻⁵10⁻³10⁻¹⁰10⁻⁸10⁻⁶magnitudespacing to the next numberthe smallest normalgradualflush to zerosmallest normal6.1·10⁻⁵smallest subnormal6·10⁻⁸octaves of subnormals10pairs that lie under FTZ10the spacing stops halving and stays putwhich is what makes x − y = 0 mean x = y

The numbers below the smallest one

Below the smallest normal number the spacing stops halving and stays put, all the way to zero. That is what gradual underflow is, and the thing it buys is the sentence every algorithm assumes without being told — x minus y is zero only when x equals y.

arithmetic · Subnormals 10⁻³10⁻¹10¹10³01magnitude448NaN — no ∞0.0156 — the smallest normaldrawn from the format's own rulespositive finite values126largest finite value448worst round-trip error0the subnormals are the evenly spaced ticks at the lefteverything a byte can be

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.

arithmetic · Floating-point 0246810121410¹⁵10¹⁹10²³10²⁷10³¹10³⁵10³⁹10⁴³k|CAᵏB|6 exact zerosa definition that will not computestates16exact zeros6‖A‖₂, measured1146last step-to-step ratio1330range across the run2·10²⁹zero for the travel timethen ‖A‖₂ᵏ

The definition asks for more of what defeats it

The rank of a p × p Hankel matrix of Markov parameters resolves a degree of p, and it needs 2p parameters to do it. Those parameters grow like the norm of the state matrix raised to their index, so the count that buys resolution is the same count that buys dynamic range. One model, four run lengths, and a spread that runs from 10¹¹ to 10¹⁰².

reduction · Transfer function 02468101201change of units, by exponent10⁰10¹10²10³10⁴10⁶10¹⁰10¹⁶10¹⁹10²⁰10⁴⁰10¹⁵⁰as writtenafter scalinga range questionlargest finite value3.4·10³⁸predicted boundary γ1.8·10¹⁹last γ that forms10¹⁹stops where scaling fails0not a poor answerno answer at all

The units that overflow before the answer does

A change of variable that is exact in the algebra requires γ² times a matrix to be a number the format can hold. In binary64 that is a bound nobody meets by accident. In binary32 it arrives at 10¹⁹ and in fp16 at 256, and past it there is no answer rather than a poor one.

arithmetic · Overflow

Named alongside it

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

Half-precisionSignificandDynamic rangebfloat16Exponent rangeIEEE 754Unit roundoffhypotBinary32Catastrophic cancellationCondition numberEquilibration

All concepts