Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Storage — where it appears

The count of numbers a representation holds, which for a structured matrix is the quantity its structure exists to reduce. It is measured per unknown rather than in total, because the interesting claim is always about how it grows with the size, and a constant added per doubling is a logarithm.

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

n = 512, ε = 10⁻⁸least storage, at leaf16numbers per unknown there133at the largest leaf211050100150200leaf sizestored per unknown48163264stored per unknownshare in the dense blockslarge dot: the least storage availableand the dashed curve is why there is one

Two knobs on one number

The tolerance raises every block's rank and leaves the partition alone. The leaf size does the opposite — it changes how many blocks there are and does not move a single rank. Both act on the same storage, and only one of them has a best setting: at eight digits the least storage is at a leaf of 16 and the largest leaf tried costs 59 per cent more. The best leaf rises with the accuracy, from 4 at two digits to 16 at twelve, and the influence runs only that way.

hierarchy · Storage growth n = 512, ε = 10⁻⁸operations over stored numbers2cheapest leaf, arithmetic alone16cheapest leaf at 0 a block16097194291388485leaf sizeoperations per unknown48163264the arithmetic aloneand the blocks it reacheslarge dot: the cheapest leaf at this chargethe lower curve is the storage curve doubled

A second objective that is the first one doubled

Counting the operations a hierarchical product does was supposed to give the leaf size a second optimum, somewhere other than where the storage puts it. The count is 160,128, 139,904, 135,936, 155,136 and 216,064 against stored totals of 80,064, 69,952, 67,968, 77,568 and 108,032 — twice each, at every leaf, exactly. The two objectives cannot disagree, and what separates the leaf that stores least from the leaf that runs fastest is a charge of about 139 operations for reaching a block at all.

hierarchy · Storage growth 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

Named alongside it

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

Cluster treeHierarchical matrixLow-rank approximationNumerical rankToleranceAdmissibilityTruncationOff-diagonal rankOptimal-complexitySeparation ratioAsymptotic analysisFlop count

All concepts