Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Lower bound — where it appears

A quantity guaranteed not to exceed the one being estimated, which for a condition estimate means every error is in the direction that flatters the matrix. For a condition estimate it means the printed number can be arbitrarily smaller than the truth, so a matrix that looks well conditioned may only have escaped the probe.

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

0369121501122334455digits asked for, −log₁₀ εcolumns keptwhat the geometry promiseswhat the matrix costsa rank is a number of digitscolumns a decade0.55bound, a decade3.3rank at 10⁻⁸5bound at 10⁻⁸28q0.5the shape is rightand the constant is not

A rank that is a number of digits

Ask a kernel block for two digits and it costs two columns; ask for fourteen and it costs nine. The curve is a straight line at 0.55 columns a decade, and the bound the geometry gives is a straight line too — at 3.32, which is the same shape and six times the price.

hierarchy · off diagonal rank 567891003691215log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers6.8·10⁴weak, numbers6.1·10⁴strong ⁄ weak1.1the better partitionis the more expensive one

The test that costs what it saves

The partition that refuses to compress a touching pair keeps every rank at five while the other lets them climb from nine to thirteen. It also stores more numbers at every size measured — 67,968 against 61,440 at n = 512 — and which of those two facts matters is a question about how large the problem is going to get.

hierarchy · admissibility the estimator maximises this quantity over the columns it visitscolumn 1 ‹visited›12column 2 ‹the answer›114column 311.4column 411.4column 511.4column 611.4column 711.4column 811.4column 911.4column 1011.4column 1111.4column 1211.4estimate 12.0a walk that stopped earlythe estimate returned12the true 1-norm114columns visited1products with the matrix5the walk's own stopping test firedand every column it could see was smaller

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.

error · condition estimation 171319253137434910⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110²indexmagnitude|r_kk|σ_kone factorisation, two verdicts‖AP − QR‖/‖A‖1.1·10⁻¹⁶|r_nn|8.7·10⁻⁴σ_min3.7·10⁻¹²column interchanges0|r_nn| is never below σ_minso the cheap verdict errs one way only

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.

spectra · rank

Named alongside it

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

Numerical rankAdmissibilityCondition estimationCounterexampleOff diagonal rankAsymptotic analysisBlock methodsCluster treeColumn pivotingCondition numberFlop countHierarchical matrix

All concepts