Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cancellation — where it appears

The loss of significance when two nearly equal numbers are subtracted, which destroys the digits that differ and keeps the ones that do not.

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

1112131415193111.365129.731148.096166.461probes takenrunning estimate of the tracenormal±1one probe, no errorthe exact trace99±1 variance, this matrix0±1 variance, rotated57normal variance545the same spectrum in a general basiscosts the ±1 probe its whole advantage

Counting what cannot be looked at

The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.

randomised · trace estimation 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

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.

arithmetic · interval

Named alongside it

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

Condition numberDirected roundingGeneralised cross validationHilbert matrixHutchinson's estimatorInfluence matrixInterval arithmeticMatrix-freeProbabilistic boundsRandom projectionSpectral decayTrace estimation

All concepts