Condition-estimation — where it appears
Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.
An estimate that can be fooled
Nobody computes a condition number, because forming an inverse costs more than the solve did. Every library estimates it instead, from four or five products with a factorisation already in hand. The estimate is exactly right on four random matrices out of five — and there is a matrix, three distinct entries wide, on which it returns a twentieth of the truth.
The cheap rank and what it cannot see
Almost nobody computes singular values to decide a rank. The standard substitute is QR with column pivoting, read off the diagonal of R — and there is a triangular matrix on which the greedy rule makes no interchange at all, has no better column available at any step, and reports a matrix eight orders of magnitude further from singular than it is.
The tail a sample never reaches
Hager's estimator is exactly right on four random matrices in five, and that share is stable — between 80.5 and 87.5 per cent across nine sizes. The worst underestimate is not stable at all: it falls every time more matrices are drawn, from 0.746 at sixty to 0.377 at four hundred, and the matrix built to defeat the estimator sits five times below anything four hundred draws found.
Two columns see what one walk cannot
The condition estimator every library ships walks from the all-ones vector, and a matrix whose largest column cancels against that vector hides from it: at n = 24 it reports five per cent of the truth. The block estimator behind MATLAB's condest walks with two vectors, the second random. On the same matrix at three sizes it is exact on every one of twenty seeds. On four hundred random 8 × 8 matrices it is exact on 96.5 per cent where the single walk is exact on 83.0, and its worst case, 0.596, is reached in the first fifty draws and not lowered by the next 1,550. The single walk's worst was still falling at 1,600. Four vectors are exact on all 400.
A first vector nobody can build against
The matrix built to fool a condition estimator is built against one vector, the all-ones vector its walk starts from, and the block estimator escaped it by adding a second, random one. Starting the single walk from random signs instead escapes it on every one of forty seeds at every size from 8 to 48, for the same 4.3 products, and loses nothing on random matrices — 86.5 per cent exact at size 8 against 84.0 from all ones, with tails that cross between sizes. The obvious way to build against a random start, a hidden column on few rows whose signs a random vector cancels half the time, fails on every seed: the hidden column writes itself into the walk's first product and turns the walk towards it. What the block of two's second vector buys is ten points of exact share, not the escape.
The error the method already knows
Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.
Named alongside it
The objects these essays reach for when they reach for this one.
CounterexampleLower boundCondition numberMatrix normWorst-case analysisSeeded generatorSilent failureCancellationCatastrophic cancellationColumn pivotingError accumulationExact ground truth