Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Definiteness test — where it appears

The question of whether a symmetric matrix is positive definite, answered by a Cholesky factorisation completing or stopping at a pivot that is not positive. It is a verdict rather than a measurement, so it has no tolerance in it and no room for two answers to differ a little.

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

2022242628303210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²k, where the entries are near 2ᵏrelative error of the determinantas writtenfused: exactproducts need 54 bitsone rounding, the whole answertrue determinant1naive, k = 300fused, k = 301first wrong at k27sizes returning 06both forms conformand the source does not say which

One multiply the compiler removed

A determinant whose value is exactly 1, computed as exactly 0 by the expression that is written down, and exactly 1 by the same expression with the multiply and the add fused. Both forms conform to IEEE-754, both are legal compilations of the same source, and nothing in the program says which one you have.

machine · fma contraction -12-11-10-9-8024681012log₁₀ of how nearly dependent the columns areverdicts that disagreed, of 40724103which one is correctmatrices tested200verdicts disagreed26fused was right9unfused was right17lower part: thefused build was righta sign has no last digitso a verdict has nowhere to hide

A matrix that is definite on one machine

Two hundred Gram matrices, two conforming builds, and twenty-six of them get different answers to "is this positive definite". The exact verdict, from determinants in BigInt rationals, says the fused build is right nine times and the other one seventeen.

machine · fma contraction

Named alongside it

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

Expression contractionFused multiply-addBitwise reproducibilityCatastrophic cancellationCholesky factorisationCondition squaringDeterminantError-free transformationExact arithmeticGram matrixIEEE 754Positive definite

All concepts