A quarter of the leaf

A hierarchical matrix stores the far-apart blocks of a kernel matrix at low rank and the near ones densely, and the leaf size — the side at which the cluster tree stops splitting — decides where one gives way to the other. Two knobs on one number found it the one setting with a best value: too small a leaf and every block pays the low-rank form’s two factors where a dense block would have been cheaper; too large, and dense diagonal blocks store what compression could have saved. At eight digits the best leaf was 16 and the largest tried cost 59 per cent more. A prediction that arrives a decade late then moved the kernel and found the best leaf nearly still: a rougher kernel raised every rank, but by at most a factor of two, and the optimum moved only at twelve digits, a decade later than the argument said it should.

That essay closed on the conjecture its numbers suggested but could not test on nine points. The break-even between a dense block and a compressed one depends on the block’s rank and nothing else, so the best leaf should depend on the mean rank alone — a kernel and a tolerance giving mean rank 8 should want the same leaf however they got there — and a table of best leaves should collapse onto one curve when plotted against it. It also proposed a kernel of a different shape, a fractional power, predicted to raise its rank without the oscillation’s factor-of-two cap and to move the optimum at eight digits after all.

Thirty cells now test both. The collapse happens, in a coordinate slightly different from the one proposed, and the fractional power does the opposite of what was predicted.

The earlier picture is the right place to start, because it is the one the collapse has to explain. Four kernels whose largest ranks differ by a factor of two had nearly the same best leaf, and the essay’s account was that the largest rank is the wrong statistic: what a halving of the leaf saves or costs is summed over many blocks, and it is the mean over those blocks that decides. That account is what the thirty cells now test, with two kernels added at the ends of the range of ranks.

Thirty cells #

The matrix is $f(\lvert x_i - x_j\rvert + \delta)$ on 512 points of the unit interval, clustered by bisection, partitioned with strong admissibility — a block is compressed only when its two clusters are well separated — and every admissible block truncated to the stated relative tolerance by its singular values. Six kernels: $1/r$ and $\log r$ as before; $\cos(40r)/r$ and $\cos(120r)/r$, the oscillatory pair; $\sqrt r$, the proposed fractional power; and $e^{-5r}$, whose off-diagonal blocks have rank exactly one at every accuracy because it is semiseparable. Five tolerances from $10^{-4}$ to $10^{-12}$. Five leaves, 4 to 64. At each of the thirty kernel-and-tolerance cells, the stored total at each leaf, the leaf that stores least, and the mean rank of the compressed blocks at every leaf.

At $10^{-8}$ the mean ranks spread the way the earlier essays found. The smooth kernels’ are flat in the leaf once it passes 4: $1/r$ at 4.7, $\sqrt r$ at exactly 4.0, $\log r$ creeping from 3.9 to 4.7, and $e^{-5r}$ at exactly 1.0 at every leaf. The oscillatory kernels’ climb: $\cos(40r)/r$ from 4.5 at a leaf of 4 to 7.9 at 64, $\cos(120r)/r$ from 4.9 to 9.3. A block at the bottom of the tree is small, and a small block cannot hold many oscillations; a larger leaf’s bottom blocks hold more, and their rank shows it.

The table, read at a fixed leaf #

Plotted against the mean rank at a leaf of 16, the conjecture is nearly right. The best leaf is 4 for the rank-one exponential at every tolerance, 8 for every cell with a mean rank of 3.67 or less, 16 for every cell at 4.67 or more, and 32 for the one cell at 9.7, $\cos(120r)/r$ at twelve digits. A staircase.

But not quite one curve. Between 4 and 4.7 the steps blur. $\cos(120r)/r$ at $10^{-4}$ has a mean rank of 4.56 at a leaf of 16 and wants a leaf of 8; $1/r$ at $10^{-8}$ has 4.67 and wants 16. Three cells in the same band tie between 8 and 16. Two cells a tenth of a rank apart wanting different leaves is not noise — the measurement is deterministic — so the coordinate is missing something.

It is missing where the rank is read. On a smooth kernel the mean rank hardly depends on the leaf and it does not matter. On an oscillatory kernel it does: $\cos(120r)/r$ at $10^{-4}$ has mean rank 4.56 at a leaf of 16 and 4.08 at a leaf of 8. The decision between a leaf of 16 and a leaf of 8 is a decision about the blocks a leaf of 8 would create, so it is their rank that matters, and for this kernel it is half a rank lower than the fixed-leaf reading says.

The rule the break-even gives #

The arithmetic is a line. Take a dense diagonal block of side $s$ and halve the leaf: it becomes two dense diagonal blocks of side $s/2$ and two off-diagonal blocks of side $s/2$ stored at rank $k$. The first stores $s^2$ numbers; the second stores $2(s/2)^2 + 2\cdot 2\,(s/2)\,k = s^2/2 + 2sk$. The halving pays exactly when

$$k < \frac{s}{4},$$

where $k$ is the rank at the finer leaf. That is the break-even the earlier essay stated — a block is worth compressing when its side is more than twice its rank — applied to the blocks the halving creates. As a rule for the best leaf: start at the largest leaf and halve it while the mean rank at half the leaf is below a quarter of the current leaf.

It predicts the best leaf on 28 of the 30 cells, counting a tie as agreement when the rule names one of the tied leaves. The two it misses are $\cos(120r)/r$ at $10^{-4}$, whose mean rank at a leaf of 8 is 4.08 against a threshold of 4, and $\cos(120r)/r$ at $10^{-10}$, whose mean rank at a leaf of 16 is 8.12 against a threshold of 8 — two per cent and one and a half per cent from the line. At both, the two leaves in question store within three per cent of each other: 69,408 against 70,400 numbers at $10^{-4}$, 111,040 against 113,920 at $10^{-10}$. The rule is right everywhere the arithmetic has a margin, and where it has none, the storage does not care much which leaf is chosen.

The ties confirm it from the other side. The three cells that tie between 8 and 16 — $\log r$ and $\sqrt r$ at $10^{-8}$, $\cos(40r)/r$ at $10^{-6}$ — have mean ranks at a leaf of 8 of 4.05, 4.00 and 4.25: on the threshold or within a few per cent of it, where the rule says the two leaves should cost about the same, and they cost exactly the same, to the number.

The curves the rule is reading #

Drawn as storage curves, each normalised to its own minimum, the rule is visible as the place each curve turns. At $10^{-8}$ the exponential kernel’s curve rises from its leftmost point, because a rank of one makes every halving pay down to the smallest leaf tried; $\sqrt r$ and $\log r$ are flat between 8 and 16 and rise either side; $1/r$ and both oscillatory kernels have their minimum at 16. Turn the dial towards twelve digits and the minima move right one kernel at a time, each when its own rank at the finer leaf crosses the line, until $\cos(120r)/r$ is the first to want 32. Turn it towards four digits and they move left, until everything but the exponential wants 8.

So the table collapses. The best leaf is a function of one number per cell — the mean rank at the finer leaf, against a quarter of the leaf — and the curve it collapses onto is a staircase whose steps are at ranks of 2, 4 and 8 for leaves of 4, 8 and 16, which is the arithmetic of dense against low-rank storage and nothing else. The earlier essay’s instinct that the mean rank decides the leaf was right; its suggestion that any reading of the mean rank would do was not.

Two knobs that turn out to be one #

The table has two axes, the kernel and the tolerance, and the rule reduces both to one number. That is worth dwelling on, because the earlier measurements treated them as separate knobs with separate effects. The partition that does not move found that the tolerance raises every block’s rank — by one per two decades of accuracy on $1/r$, which the offset that moved the slope first measured as a growth rate — and leaves the partition exactly where it was. The earlier essay on kernels found that roughness multiplies the rank by up to two and does the same. Both knobs move the leaf only through the rank.

So a cell’s position on the staircase is decided by one quantity, and cells with very different kernels and tolerances can sit on the same step. $1/r$ at $10^{-6}$, $\cos(40r)/r$ at $10^{-4}$ and $\log r$ at $10^{-6}$ all have mean ranks between 3.0 and 3.7 at the finer leaf, and all want a leaf of 8. $\sqrt r$ at $10^{-10}$, $1/r$ at $10^{-8}$ and $\cos(120r)/r$ at $10^{-6}$ have 4.7 to 5.4 and all want 16. The kernel matters exactly as much as it changes the rank, and so does the tolerance, and neither has any other channel. A leaf tuned for one kernel at one accuracy has, without anyone intending it, been tuned for every kernel and accuracy that lands on the same step — and a leaf tuned by trial on a kernel whose ranks sit near a threshold is the one choice that will not transfer, since a neighbouring kernel a fraction of a rank away can fall on the other side of it. A rank that is a number of digits made the same point about a single block — its rank counts the digits asked of it — and the staircase is that point summed over a partition.

The fractional power was smoother, not rougher #

The earlier essay predicted that a kernel of a different shape — a fractional power, not a bounded-rank factor times a smooth kernel — would raise its rank without the oscillation’s factor-of-two ceiling, keep its mean rank flat in the leaf because it introduces no length of its own, and so move the optimum at eight digits where the oscillations could not.

Half of that holds. $\sqrt r$’s mean rank is flat in the leaf, 4.0 at every leaf from 8 to 64 at $10^{-8}$, as a kernel with no length of its own should be. But its rank is lower than $1/r$’s, not higher: 2.0, 3.0, 4.0, 5.0 and 5.7 at the five tolerances against $1/r$’s 2.7, 3.7, 4.7, 5.7 and 6.7. So it does not move the optimum later than $1/r$ does; it moves it no later than $\log r$ does, and ties at eight digits where $1/r$ has already moved to 16. The singularity the shifted kernel $\sqrt{r + \delta}$ carries at the diagonal is weaker than $1/(r + \delta)$'s, and a weaker singularity is fewer digits of rank for a separated block, not more.

The kernel that does move the optimum is the one with rank one: $e^{-5r}$, whose off-diagonal blocks are exactly rank one at every accuracy, wants the smallest leaf tried at every tolerance, and would want a smaller one still. It is the other end of the staircase from the kernel with nothing to compress, where the rank is full and no leaf is best because no block compresses.

What the rule is worth in practice #

The rule needs the mean rank at a leaf that has not been built. In practice an implementation chooses its leaf once, from the kernel and the tolerance, before it compresses anything, and what it needs is a way to guess the rank. The measurements say how good a guess has to be. Away from the thresholds — ranks of 2, 4 and 8 — the best leaf is insensitive to a rank error of a unit or so; near them, the two candidate leaves store within a few per cent of each other and a wrong guess costs a few per cent. A rank guess good to one unit is therefore enough to choose a leaf within a few per cent of the best, on every cell here.

The earlier essays found where such a guess could come from: a rank that is, on a smooth kernel, one per two decades of tolerance, and a factor of two for an oscillation. A second objective that is the first one doubled found that the operation count of a hierarchical product is exactly twice the storage at every leaf, so the rule chooses the leaf for the arithmetic as well as for the memory.

What this does not settle #

One size, 512 points, in one dimension, with strong admissibility and a separation constant of 0.8. A geometry setting that is a second accuracy found that constant moving both the number of blocks and their ranks, from 592 blocks at mean rank 3.25 to 94 at 8.94 across its range, so a different constant moves every cell along the staircase — the rule should follow it, since it reads the rank, but that is not measured. The break-even arithmetic above is the weak-admissibility version — two dense halves and two compressed off-diagonal blocks — and strong admissibility keeps neighbouring blocks dense at the finest level. That the weak rule predicts the strong partition’s best leaf on 28 of 30 cells is measured, not derived; in two or three dimensions, where a cluster has many neighbours kept dense, the constant a quarter need not survive.

The mean rank is a mean. A partition whose ranks are spread — a few blocks near the diagonal at high rank and many far away at low rank — could have a mean that sits below the threshold while the blocks that the halving actually creates, which are the near ones, sit above it. The kernels here do not separate those, and the rule’s two misses at one and two per cent from the line may be the first sign of it.

Still open: the rule in two dimensions, and the rank a code can guess #

A second dimension. In one dimension a cluster has two neighbours; in two it has eight, and under strong admissibility all of them are kept dense at the finest level. The halving arithmetic then trades two dense halves against a number of dense neighbour blocks as well as compressed far ones, and the threshold is no longer a quarter of the leaf. Deriving it for a two-dimensional grid and checking it against the best leaf on a two-dimensional kernel would say whether the staircase is a fact about hierarchical matrices or about intervals.

The rank before the compression. The rule reads a rank an implementation does not yet have. It has the kernel, the tolerance and the geometry, and the earlier essays found the rank to be about one per two decades of tolerance on a smooth kernel, doubled by an oscillation. Whether that guess, fed to the rule, chooses the same leaf as the measured rank on all thirty cells — or which ones it gets wrong — is the measurement that would turn the rule into something that could be run before anything is built.