Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Black box construction — where it appears

A representation assembled from products with a matrix rather than from its entries, which are never read. The operator is applied to random vectors and the results are peeled into low-rank blocks, so the cost is counted in products and the accuracy is a property of the sample.

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

567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48‖A − A_H‖ ⁄ ‖A‖4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read

Built from products alone

A 512-square hierarchical representation, at a relative error of 4·10⁻⁷, from 256 applications of an operator that is never assembled. The compression route reads 262,144 entries; this one reads none, and pays for it with a factor of seven against the representation the entries would have given.

randomised · Sketching 048121610⁻⁸10⁻⁷10⁻⁶10⁻⁵extra columns in the sample, p‖A − A_H‖ ⁄ ‖A‖the best rank-8 representationfive draws, mean and rangea band, not a lineexcess at p = 012excess at p = 83spread at p = 00.44spread at p = 80.12the optimum of this rank7.8·10⁻⁸one seed shows the meanand five show the risk

What a single draw cannot report

With no oversampling the construction's error is 11.6 to 50 times the best representation of the same rank, and the spread across five seeds runs from 16 to 146 per cent of the mean. Sixteen extra columns bring the excess to between 2.0 and 2.9 at every rank measured and the spread to between 4 and 20 per cent — and the second number is the one a single run cannot report and the one that decides whether the first is a measurement.

randomised · Sketching

Named alongside it

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

Hierarchical matrixOff-diagonal rankOversamplingRandomised SVDRange finderAdmissibilityMatrix-freeProbabilistic boundsRandom projectionRelative errorRun-to-run variationSeeded generator

All concepts