Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Separation ratio — where it appears

The size of two clusters of points relative to the distance between them. A hierarchical matrix's admissibility test compares it against a constant, before any entry of the matrix is read, to decide whether the block between those clusters may be compressed. Holding it below one threshold is what bounds every compressed block's rank.

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

n = 512, leaf 16blocks, tightest to loosest592and at the loosest94mean rank, tightest3.3and at the loosest8.9052104156208260the separation constantstored per unknown0.20.30.40.50.951.4stored per unknownmean rank, compressed blocksboth curves move togetherwhich is what the other two knobs never do

A geometry setting that is a second accuracy

The tolerance raises every rank and moves no block; the leaf moves every block and no rank. The constant that decides how far apart two clusters must be before their block may be compressed moves both — 592 blocks at mean rank 3.25 at one end and 94 at mean rank 8.94 at the other — and the storage falls the whole way while the error against the dense matrix rises by a factor of 3.5, at a tolerance that never changed. It has no best setting, and it is not a third knob on the storage.

hierarchy · Storage growth n = 512, ε = 10⁻⁸1/r, least at leaf16log r, least at leaf8cos(40r)/r, least at leaf16cos(120r)/r, least at leaf1604794141188235leaf sizestored per unknown481632641/rlog rcos(40r)/rcos(120r)/rthe rank doubles and the optimum does not movewhich the next figure explains

A prediction that arrives a decade late

A rougher kernel raises every rank, a higher rank raises the side at which compressing a block stops paying, so the leaf that stores least should rise. Across four kernels whose largest rank runs 5, 5, 9 and 10, it is 16 on three of them and a tie between 8 and 16 on the fourth. The prediction is right in sign and out by a decade of tolerance, and the reason is a ceiling: an oscillation multiplies the rank by exactly two — 3 and 6, 4 and 8, 5 and 10, 6 and 12, 7 and 14 — at any frequency, because a cosine of a difference is a rank-two function.

hierarchy · Storage growth k < s/4cells agreeing28cells3010⁻³10⁻²10⁻¹11distance from the threshold, relativepredicted leaf ÷ bestred: the rule's two missesboth within three per cent of the break-even

A quarter of the leaf

The leaf that stores a hierarchical matrix most cheaply had been read off a table of nine points, with the suggestion that it depends on the mean rank alone. Across six kernels at five tolerances — thirty cells — it does, once the mean rank is read in the right place. Plotted against the mean rank at a fixed leaf of 16, two cells a tenth of a rank apart want leaves of 8 and 16. Plotted against the rank of the blocks a halving would create, one rule — halve the leaf while that rank is below a quarter of the leaf — predicts the best leaf on 28 of the 30, and the two it misses are the two whose rank sits within three per cent of the threshold. The fractional power the last measurement expected to be rough is smoother than 1/r.

hierarchy · Storage growth

Named alongside it

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

AdmissibilityCluster treeHierarchical matrixLow-rank approximationNumerical rankStorageToleranceOff-diagonal rankTruncationWeak admissibility

All concepts