Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Precision as the knob — page 2

Essays 25 to 31 of the 31 on this theme, in the same order.
56789100108216324432log₂ nnumbers stored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5126.8·10⁴weak, n = 5126.1·10⁴dense, n = 5122.6·10⁵per doubling26‖A − A_H‖ ⁄ ‖A‖3.8·10⁻¹⁰the dense line doublesand the other two add a constant Neither sparse nor dense

The offset that moved the slope

The accuracy is supposed to lift a storage curve and leave its growth alone. Measured at seven tolerances, the strong partition adds 10.9 numbers per unknown per doubling at two digits and 36.5 at twelve — the growth rate more than triples, so ten decades of accuracy cost 33 per cent more storage at 64 unknowns and 118 per cent at 512.

 entries rounded to zero, of 320block, as given310block, sorted by size22E4M3, either order0median entry's relative errorblock, as given1block, sorted0.00321E4M30.022the same numbers, three waysdeleted, as given310deleted, sorted22deleted, per-element08-bit significands, blocks of 32sorting is free and changes no value The arithmetic underneath

A bit buys an octave

The outlier a block survives is exactly two raised to its significand width — 8 at three bits, 32 at five, 128 at seven, 512 at nine. Each extra bit doubles the range the block tolerates and halves the ordinary entry's error. Reordering the same numbers buys every octave at once and costs nothing.

 10⁻⁹10⁻⁶10⁻³110³10⁶13212937κ · usignificand bitsκu = 1a bound was provedthe method refusedit never returns a wrong boundlargest κu with a proof0.45smallest κu without one0.89cases refused, of the grid13a refusal is not a wide bound — it is no bound at alland it is the only failure mode here The arithmetic underneath

A bound that is proved

Every error statement on this site so far 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.

 11.522.511.52xyexactly one roota verdict, not a bound‖I − C F′(X)‖0.28width of X0.8width of K(X)0.23strictly inside is a proofand overlapping is nothing at all The arithmetic underneath

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.

 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 arithmetic underneath

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.

 036912151810¹10²10³rotationswidththe enclosurethe seta rotation is an isometrymeasured growth a step1.4√2, from the geometry1.4enclosure ÷ set after 201024no rounding error is responsible for any of thisa higher precision does not touch it The arithmetic underneath

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.

 614223038465410⁻¹³10⁻¹⁰10⁻⁷10⁻⁴working significand bitsrelative sizeerrorresidualuthe gap the solver cannot seeerror ÷ residual at 24 bits1.5·10⁶error ÷ residual at 16 bits2.3·10⁷error ÷ residual at 8 bits2.4·10¹⁰every convergence test passesand the answer is wrong in proportion to u The answer that depends on the machine

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.

All themes