Two knobs on one number

The partition that does not move separated the two things that could have been moving a hierarchical matrix’s storage growth and found only one of them moving. The partition — 250 blocks at n = 512, 156 low-rank and 94 dense — is identical at every tolerance from 10⁻² to 10⁻¹², because it is decided by the cluster tree’s geometry before any singular value is looked at. What the tolerance moves is the rank, by exactly one per two decades, and the slope is 5.11 numbers per unknown per doubling per unit of it.

Which leaves the other half of the product unexamined. The storage is a count of blocks times what each holds, and the tolerance decides the second factor and nothing about the first. Something decides the first, and it is the leaf size of the cluster tree — the point at which the recursive bisection of the points stops and a block is stored densely.

Two knobs on one number, acting on different factors of it. They do not behave the same way.

The leaf changes the count and not the ranks #

A block nobody can call sparse is where the ranks this sweep holds fixed were first measured, and the kernel with nothing to compress is the case in which none of what follows applies.

At eight digits and n = 512, leaves of 4, 8, 16, 32 and 64 give 532, 250, 112 and 46 blocks — the tree has fewer levels, so there are fewer of everything — and store 156, 137, 133, 152 and 211 numbers per unknown.

The largest rank is 5 at every one of them. Not close to 5; exactly 5, at every leaf.

That is the mirror image of that measurement’s finding and it has the same cause read backwards. A block’s rank is decided by how fast its singular values fall, which is decided by how far apart its two clusters are relative to their diameters — and the admissibility test admits a block precisely when that ratio clears a threshold. So every admissible block, at every level of every tree, has roughly the same separation ratio by construction, and therefore roughly the same decay, and therefore the same rank at a given tolerance.

Changing the leaf changes how many such blocks there are and at what sizes. It does not change what any of them costs per unit of side.

The offset that moved the slope held the leaf fixed at 16 throughout, which is the value this sweep finds best at eight digits — so every number that measurement reported is at or near the leaf’s optimum and none of them is an artefact of a badly chosen tree. That is worth checking rather than assuming, because a sweep of one knob at a bad setting of another measures the second knob’s badness.

And that is why there is an optimum #

A smaller leaf means more blocks, which means more low-rank blocks — 342 of them at leaf 4 against 24 at leaf 64 — each storing rank × (rows + columns), and more of the matrix covered by low-rank blocks rather than dense ones. The share of the storage sitting in the dense diagonal blocks falls from 83 per cent at leaf 64 to 17 per cent at leaf 8.

That pulls one way: smaller leaves compress more of the matrix. It pulls the other way through the bookkeeping. Each low-rank block of rank r on sides m and k stores r(m + k) where a dense one would store mk, and the saving mk − r(m+k) is negative when the block is smaller than about 2r on a side. At rank 5 that is a block of 10, so leaves below about 10 produce blocks the compression makes larger.

The two effects cross somewhere, and at eight digits they cross between 8 and 32, with 16 the least of the five tried at 133 numbers per unknown against 211 at leaf 64 — 59 per cent more.

The optimum moves with the accuracy, in the direction nobody would guess #

The crossing depends on the rank, so it should move with the tolerance, and the interesting question is which way.

The intuitive answer is that a tighter tolerance wants a smaller leaf: more digits means the representation has to work harder, and working harder means compressing more of the matrix. Measured over five leaves at six tolerances, the leaf minimising storage is 4, 8, 8, 16, 16 and 16 as the accuracy goes from two digits to twelve.

It rises. A tighter tolerance wants a larger leaf.

The reason is the inequality above. A low-rank block is worth having when mk > r(m+k), and raising r makes that harder to satisfy — so blocks that were worth compressing at rank 2 are not worth compressing at rank 7, and the smallest blocks fall out of the useful range first. A larger leaf is exactly the tree that does not create them.

So the two knobs interact, and the interaction is one-directional. The tolerance moves the best leaf; the leaf does not move any rank. That asymmetry is worth having explicitly because it says how to tune: choose the tolerance from the application, then choose the leaf, and never the other way round.

It is worth being precise about the crossing, because the inequality is exact and the conclusion is not.

A block of m by k costs mk dense and r(m + k) compressed, so compression pays when r < mk/(m + k) — which for a square block of side s is s/2. At rank 5 the break-even side is 10; at rank 7 it is 14. The blocks a tree of leaf ℓ produces have sides ℓ at the bottom and 2ℓ, 4ℓ and so on above, so a leaf of 8 at rank 7 produces bottom-level admissible blocks of side 8, below the break-even of 14, and every one of them is stored larger than it needs to be.

That is the mechanism, and it accounts for the direction and not for the exact optimum — because the partition also has fewer blocks at larger leaves, and the bottom level is only one of several. The measured optimum is where the two effects balance over the whole tree, which is a sum the inequality does not evaluate.

What the leaf costs beyond storage #

The size the rank does not notice is the single-block version of the invariance this sweep finds across a whole partition. Storage is one of three things a leaf size decides and it is the only one measured here, so it is worth naming the other two rather than leaving them implied.

A larger leaf means fewer, bigger dense blocks, which a machine multiplies faster per number — the same argument that makes blocked factorisations worth their extra arithmetic. At leaf 64 the dense blocks are 64 by 64, which is a level-3 operation; at leaf 4 they are 4 by 4, which is not. So the leaf that minimises stored numbers is not the leaf that minimises seconds, and the gap between them points toward larger leaves.

A larger leaf also means a shallower tree, which means fewer levels for the recursive algorithms — the hierarchical solve, the addition, the multiplication — to walk. That points the same way.

Both of those would move the practical optimum right of the storage optimum, and neither is measured here. What the storage sweep establishes is the left end of the range worth considering: below leaf 8 at any tolerance, and below 16 at twelve digits, the representation is storing more numbers and doing worse on both of the other counts, which is not a trade at all.

Why the ranks not moving is the surprising half #

The optimum and its direction are the findings a practitioner would want. The measurement that makes them interpretable is the flat one: maximum rank 5 at leaves 4, 8, 16, 32 and 64.

It is not obvious. The blocks at leaf 64 are sixteen times the area of those at leaf 4, and a larger block of a smooth kernel has more structure in it, so a reader would reasonably expect the rank to grow with the block. It does not, because the rank is set by the ratio of separation to diameter and the admissibility test holds that ratio fixed — a bigger block is admitted only when its clusters are proportionally further apart.

That is the same statement which pairs are allowed to be small makes about the test, and the size the rank does not notice measures directly for a single block and is the reason a hierarchical representation works at all. What this sweep adds is that the invariance is exact enough to survive a sixteenfold change in block area without moving an integer.

So the two knobs really are on different factors, and the product decomposes: storage per unknown is (blocks per unknown, decided by the leaf) times (numbers per block, decided by the tolerance) plus the dense part, which the leaf decides and the tolerance does not touch.

What a code should do with two knobs of different characters #

The measurement supports a tuning order and it is worth writing down because the intuitive one is backwards.

The tolerance comes from the application: it is how accurate the representation has to be, and nothing about the data structure should influence it. The earlier measurement established that it sets every block’s rank and touches nothing else, so choosing it first costs nothing.

The leaf then follows from the rank through the break-even inequality — below about twice the rank a compressed block is larger than a dense one — which gives a lower bound, and from whatever the machine wants for its dense blocks, which gives a preference upward. So: read the tolerance, compute the rank it implies, set the leaf above twice it, and go higher if the dense-block arithmetic is worth more than the stored numbers.

What the order must not be is the reverse. A leaf chosen first and a tolerance chosen second leaves the leaf at whatever the rank makes wrong — and the measurement says wrong by up to 59 per cent in storage, which is the whole of what a hierarchical representation was adopted for.

The partition that does not move is what makes the order safe. Because the tolerance cannot change the partition, choosing it first cannot invalidate a leaf chosen afterwards; if the influence ran both ways the two would have to be optimised together.

What must fail for any of this to be wrong #

Five claims and a refusal. That the largest leaf is never the best, at three tolerances spanning ten decades. That it is substantially worse — at least 30 per cent — at each. That the dense share rises with the leaf, which is the mechanism. That the ranks do not move with the leaf at all, which is the mechanism’s other half. And that the best leaf rises with the accuracy, from 4 at two digits to 16 at twelve.

The refusal is fed the claim that the best leaf at twelve digits is no larger than at two.

The sweep also re-checks that measurement’s monotonicity — that the tolerance raises the slope at every step — inside the same function, so the two knobs’ different characters are established by one measurement rather than by two that have to be compared.

What this does not settle #

One kernel, one point distribution, one admissibility rule, one size for the leaf comparison. The 59 per cent is the spread over the five leaves tried at eight digits and n = 512.

Five leaf sizes, powers of two from 4 to 64, so the optimum is located to a factor of two. A finer sweep would place it better and would not change which side of it the largest leaf is on.

Storage only. The two arguments above for larger leaves — dense blocks that multiply faster and a shallower tree — are stated and not measured, and either could move the practical optimum by more than the factor of two this sweep resolves.

And the leaf enters the admissibility test through the cluster tree it builds, so a very large leaf produces a tree with few levels and few admissible pairs at all. At leaf 64 on 512 points there are three levels and 24 low-rank blocks, which is close to the regime where the representation stops being hierarchical and becomes a block matrix with a few compressed corners.

What the sweep says about the representation itself #

One reading of the leaf curve is about the leaf and another is about the thing the leaf is a parameter of, and the second is the more useful.

At leaf 64 on 512 points the tree has three levels and 24 low-rank blocks, and 83 per cent of the storage is in 22 dense blocks of 64 by 64. That is not a hierarchical matrix in any interesting sense; it is a block matrix with a few compressed corners, and it stores 211 numbers per unknown against the dense matrix’s 512 — a saving of 59 per cent where leaf 16 saves 74.

At leaf 4 the tree has eight levels and 342 low-rank blocks, most of them 4 by 4 or 8 by 8, and 17 per cent of the storage is dense. That is a hierarchy with nothing useful at its bottom: blocks so small that compressing them to rank 5 stores more numbers than keeping them.

So the curve’s two ends are two different failures of the same idea — too coarse to be hierarchical, and too fine for the hierarchy to be worth anything — and the minimum between them is where the structure is doing what it is for. A practitioner asking “is my leaf right” has, in the shape of this curve, the answer: if the dense share is near 80 per cent the tree is too shallow, and if the smallest blocks are under twice the rank it is too deep.

Both of those are readable off a representation without a sweep, which is the practical version of the finding. The dense share is a sum the representation already carries, and twice the rank is a number the tolerance implies.

Still open: the leaf in seconds, the finer sweep, and the third knob #

The leaf that minimises time. Storage is the quantity these essays is named for and is not the quantity anybody optimises. A measurement counting the operations a hierarchical matrix–vector product does — which is a sum over blocks of 2mk for dense and 2r(m+k) for low-rank — would have a different optimum, and the difference between the two optima is the number a code would want.

A finer sweep. Five leaves at powers of two locate the optimum to a factor of two. Sweeping 4 through 32 in steps of two would say whether the minimum is flat — in which case the choice hardly matters and the finding is that the range is wide — or sharp.

The separation threshold as a third knob. η decides how far apart two clusters must be to be admissible, and it moves the ranks and the block count, which is what neither of the two knobs here does. That makes it the one parameter that could break the decomposition this essay rests on, and it is the obvious next thing to sweep.

And whether the invariance of the rank survives a rougher kernel. Rank 5 at every leaf is a statement about a smooth kernel whose singular values fall a hundredfold per index. On a kernel with slower decay the rank would be higher and the crossing between low-rank and dense would move to larger blocks, which should push the optimal leaf up further — a prediction with a sign, and one sweep.