The test that costs what it saves

The previous essay put a test in the partition and did not say what it was worth. This one measures both sides of it, and the two sides point in opposite directions.

The two partitions, side by side #

Same matrix, same points, same accuracy, same leaf size, at four sizes:

Read the rank columns and the test is obviously worth having: five at every size against a number that climbs by one per doubling. Read the storage columns and it is obviously not: the partition with the bounded rank costs more at every size, by between eight and thirteen per cent.

Both readings are correct and the second is the one nobody expects, which is why it is the finding rather than a footnote.

Where the extra storage goes #

The strong partition has two and a half times as many blocks and they are smaller. That is the whole of it, and it costs in two places.

The dense fringe. Refusing to compress a touching pair means subdividing it — the same fill-against-growth trade a sparse pivot rule makes, with a geometric test in place of a numerical one — and the subdivision terminates on leaves that are stored entry by entry. At n = 512 the strong partition keeps 106 dense blocks against the weak one’s 32 — because every touching pair, at every level, eventually becomes four leaf-sized dense squares. Those are small individually and there are a great many of them.

The rank floor. A compressed block never has rank zero. A 32 × 32 block at rank 5 stores 320 numbers against 1,024 entries, which is a saving of a factor of three; a 256 × 128 block at rank 12 stores 9,216 against 32,768, a factor of three and a half. The saving from a low-rank block is 2k/n in the block’s own size, so small blocks compress badly, and a partition made of small blocks is a partition that compresses badly even when each of its ranks is tiny.

So the test trades a rank that grows slowly for a block count that grows quickly, and at these sizes the block count is winning.

When the other reading wins #

The asymptotic argument is not wrong, it has simply not arrived yet, and it is worth saying exactly what it needs.

The weak partition’s cost is O(n log²n) rather than O(n log n), because its rank carries a log of its own. At n = 512 with a leaf of 16 there are five levels, so the extra log is a factor of five — and a factor of five inside an asymptotic constant is invisible against a twelve per cent difference in the measured totals. The crossover is where the weak partition’s rank has grown enough to overwhelm the strong one’s block count.

Where the crossover is, which does not need a larger computation #

Extrapolating “far past any size this site can compute” is the tempting way to leave it, and the two columns already contain the answer. Numbers stored per unknown, against L = log₂ n:

   n        64     128     256     512        fitted
 strong     54      79    105.5   132.75    −104.25 + 26.27·L
 weak       50      70     94     120       −9.50 + 0.90·L + 1.50·L²

A straight line against a parabola — which is exactly the O(n log n) against O(n log²n) the paragraph above asserts — and both fits land on all four points to under half a number per unknown. Solving for where they meet gives L = 11.4, or n ≈ 2,600. Refitting on different subsets of the four points moves it between 1,700 and 5,800.

Two to three and a half doublings past the largest size drawn. That is not far past anything computable; it is one afternoon on a bigger machine, and it is a small problem by the standards of the field this format exists for.

Which settles the guess this essay was about to make. At ten thousand unknowns the fits put the weak partition at 267 numbers per unknown against the strong one’s 245 — ahead by nine per cent rather than behind. The simpler partition is not still cheaper there; it stopped being cheaper somewhere around a few thousand, and every size anybody actually runs this format at is on the other side of the crossing from every size drawn in this essay.

That changes what the table is evidence for. It is not evidence that the simple partition wins in practice and loses asymptotically; it is evidence that the measurement is being taken inside the pre-asymptotic region, three doublings from its edge, and the ordering it shows reverses just past the right-hand end of the axis. Which is the honest reading of a four-point extrapolation and is a sharper statement than “the crossover is somewhere out there”.

There is a caution to keep with it, because a four-point extrapolation is a four-point extrapolation. The weak curve’s quadratic coefficient is 1.50 and it is fitted from four numbers; a second-order term estimated that way is the least reliable part of the fit, and the spread of 1,700 to 5,800 across subsets is an honest error bar rather than a formality. What the fit is reliable about is the sign and the order: the weak curve bends upward, the strong one does not, and the crossing is thousands rather than millions.

The reason that distinction is worth making is what it does to the advice. A crossover at ten million would say: use the simple partition, the asymptotic argument is a theoretical curiosity for the sizes anybody runs. A crossover at a few thousand says the opposite — the asymptotic argument is the operative one and the measurement in this essay is the curiosity. Nothing in the table changes, and what it is evidence for reverses.

That is the general hazard of measuring a trade at the largest size available. The size available is chosen by what the measurement can afford, and the crossover is chosen by the problem; there is no reason for the first to be past the second, and every reason — since an expensive measurement is a small one — for it not to be. Locating the crossing, rather than reporting the ordering at the sizes reached, is what turns the measurement into something a reader can carry to a problem of their own size.

The rank is not only a storage cost #

The table above prices a rank in numbers stored, which under-counts it, and the under-counting is why the asymptotic argument is worth taking seriously earlier than the storage says.

Every operation in a formatted arithmetic costs more than linearly in the rank. Multiplying two rank-k blocks costs O(k²n); adding two of them and recompressing costs O(k²n) for the orthogonalisation and O(k³) for the small decomposition; a formatted factorisation does a great many of both. So a rank of 13 against a rank of 5 is a factor of 2.6 in storage and a factor of nearly 7 in the arithmetic of every operation that touches those blocks.

A representation that is only ever multiplied by vectors does not care: a matrix–vector product is linear in the rank, and the storage table is the whole story. A representation that is going to be inverted, or squared, or used to build a formatted factorisation, cares a great deal, and a kernel with nothing to compress is the case where neither partition helps at all.

Which is the same sentence the previous essay ends on and the one this whole field keeps arriving at: a format is chosen for what is going to be done to it, and a comparison that prices only storage has priced the easiest thing anybody does with it — which is the same arithmetic at a different price read from the format’s side rather than the machine’s.

What each partition is actually made of #

The block counts in the table are easier to read once the two structures are named, and naming them also says why one of them has a solve and the other does not.

The weak partition is a recursion on the diagonal. At the top level there are exactly three objects: the two off-diagonal blocks, and the two diagonal blocks which are the same problem one level down. At level ℓ it contributes 2·2^ℓ compressed blocks, all of them the same size, and it terminates in 2^L dense leaves. Every compressed block is the full off-diagonal quadrant of some diagonal block. That regularity is what a formatted solve needs — at each level the off-diagonal part is one low-rank correction to a block-diagonal matrix, which is a Woodbury update — and it is why almost every code that inverts a hierarchical matrix uses this partition.

The strong partition is a recursion on pairs. It starts with the root against itself, and every pair that fails the test spawns four pairs of children. The pairs that pass become blocks; the ones that fail and have no children become dense blocks. What comes out has blocks of several sizes at each level, arranged in a band whose width is set by η, and there is no level at which the off-diagonal part is a single low-rank object.

So the extra 156 blocks at n = 512 are not overhead in the bookkeeping sense. They are a genuinely finer description of the matrix, each piece of which is genuinely cheaper than the piece it replaced — and the sum of them is larger, because a description made of many small accurate pieces is not automatically smaller than one made of few large approximate ones.

That is a sentence worth carrying out of this field. Refining a decomposition improves every piece of it and need not improve the total — the same arithmetic the order decides the memory runs on an ordering rather than on a partition, and which way it goes is arithmetic rather than principle.

The rank that climbs, read carefully #

The weak partition’s rank column — 9, 10, 12, 13 at eight digits, 12, 14, 16, 18 at twelve — is the only quantity in this field that grows with the problem, and it is worth being precise about what kind of growth it is.

It is not the whole partition’s rank. It is the largest rank anywhere in the partition, and the block carrying it is always the same one: the pair of top-level halves, which touch — the case a hierarchy with no grid behind it has to decide with no geometry to decide it with. Every other block in the weak partition is admissible in the strong sense and has a rank of five, exactly as the strong partition’s blocks do. The mean rank at n = 256 is 8.8 against a maximum of 12, and the distribution is two large numbers and twenty-eight small ones.

So the weak partition is not a worse partition everywhere. It is the strong partition plus a handful of inadmissible blocks compressed anyway, and the handful is small — two per level — which is why the total storage difference is twelve per cent rather than a factor.

That also says where the asymptotic argument bites. The number of inadmissible blocks the weak partition compresses is 2·(levels), and each of their ranks grows like the log of its own size. So the extra cost is a sum over levels of (log of the level’s size) × (the level’s size), which is where the second logarithm comes from, and it is a genuinely different asymptotic class from the strong partition’s. Being a different asymptotic class and being twelve per cent apart at n = 512 are both true, and only the second is a measurement.

The comparison this site has already made twice #

The shape here — a finer decomposition with better local properties and worse totals — is one this collection has met in two other fields, and reading the three together is more useful than any of them alone.

the-same-arithmetic-at-a-different-price is the cost field’s version: a blocked factorisation and an unblocked one perform the same multiplications in a different order, the flop counts are identical to the last operation, and the memory traffic differs by a factor that decides which is usable.

a-threshold-between-fill-and-growth is the sparsity field’s: a threshold pivoting rule trades fill against stability, the two are measured in different units, and there is no setting at which both are best.

The common structure is a trade between two resources that cannot be added up. Here it is block count against rank; there it is traffic against operations, and fill against growth. In all three the mistake to avoid is the same one — picking whichever resource the figure happens to plot — and the defence is the same: put both on the badge.

What the accuracy does to the comparison #

The tolerance is a knob on both partitions and it moves them together, which is worth checking rather than assuming.

At 10⁻² the strong partition’s ranks are 2 at every size and the weak one’s are 3 and 4, and both are storing mostly their dense fringe — so the ratio between them is set by the fringe, which is the strong partition’s weak point. It stores 17,216 numbers against 10,752 at n = 256: a factor of 1.60, and the gap is at its widest.

At 10⁻¹² the ranks are 7 against 12, 14, 16, 18 — the weak partition’s climbing three times as fast as before, because a tighter tolerance samples further down a spectrum whose tail is exactly what the touching pairs have. The totals are 33,536 against 30,720: a factor of 1.09.

The direction is the useful part. Tightening the accuracy favours the test, because a tighter accuracy makes ranks the dominant cost and ranks are what the test controls. A code that needs three digits should use the simpler partition; a code that needs twelve has a reason to pay for the finer one, at any size.

That is a cleaner rule than the asymptotic one and it is available now rather than at ten million unknowns, which is the sort of thing a measurement is for. It is also, honestly, a rule about a narrowing gap rather than a crossing one: the ratio goes 1.60, 1.12, 1.09 and does not reach one at any tolerance the arithmetic supports. What tightening the accuracy buys the test is that its cost stops mattering, not that it starts paying.

Two decades looser again, which is the range a code actually asks for when the hierarchy is being used as a preconditioner rather than as a representation:

The strong rank is 2, 3, 4, 5 and 7 at ε = 10⁻², 10⁻⁴, 10⁻⁶, 10⁻⁸ and 10⁻¹². One more rank for every two decades, which makes it log₁₀(1/ε)/2 + 1 exactly at all five stops — and flat in the size at every one of them, 3, 3, 3, 3 and 5, 5, 5, 5 and so on down the sweep. The weak rank climbs at every tolerance instead, and climbs faster as the tolerance tightens: 3 to 4 at 10⁻², 5 to 7 at 10⁻⁴, 9 to 13 at 10⁻⁸, 12 to 18 at 10⁻¹².

And the title’s claim is a curve rather than a verdict. Comparing what the two partitions store at the largest size:

The stronger test costs more at every tolerance on this sweep, and the premium falls from 55% to 8.7% as the tolerance tightens, monotonically. So the test does not yet pay for itself at these sizes — what it buys is the flat rank, which is an asymptotic property, and what it costs is a premium that is already shrinking towards nothing by the time the tolerance is at 10⁻¹². The two curves are converging, and the essay’s title is about where they cross rather than about a verdict at one ε.

The other resource, which neither column prices #

There is a third quantity in this comparison and neither of the two tables has it, so it is worth putting on the record before the verdict.

Both partitions reproduce the matrix. The strong one reaches 3.4·10⁻¹⁰ at n = 256 and the weak one 1.1·10⁻⁹, at the same ε — a factor of three, in the strong partition’s favour, at every size measured.

That is not a coincidence and it is not free either. The reason the strong partition is more accurate is the same reason it is more expensive: it keeps the touching pairs dense, so those blocks are exact, and they are the blocks with the largest entries in the whole matrix. The weak partition compresses them, at a rank chosen by the same ε as everything else, and their error is what dominates the total.

So a fair comparison would run the weak partition at a tighter ε and see what its storage becomes, which is a third table nobody wants. What can be said from the two that exist is that the twelve per cent in the storage column is bought with a factor of three in the error column, and a reader who wanted the two partitions equalised on accuracy would find the gap smaller still.

This is the standing difficulty with comparing two methods that each have a knob: there is no comparison, only a surface, and any table is a slice through it. This collection’s field about four knobs and one floor is the long version of that observation, and the shortest useful form of it is that a comparison is only honest if it says which slice it took.

The refusal #

The claim under test is the one the rank column invites: that bounding the rank of every block makes the representation cheaper.

It is not marked false. It is marked asymptotic, which is this site’s verdict for a claim that is true in the limit and not true at any size anybody has, and the distinction matters because the wrong verdict here would be as misleading as no verdict at all.

The refusal is fed the storage figures at 256 unknowns: the assertion that the strong partition stores fewer numbers than the weak one is handed 27,008 and 24,064, and it fails. It would fail at every one of the four sizes measured. What it does not do is establish that the asymptotic reading is wrong — nothing here can — and the verdict says so.