One build tells the leaf

A quarter of the leaf found the rule that sizes a hierarchical matrix’s leaves. Store the matrix as dense blocks near the diagonal and low-rank blocks far from it, and the leaf — the size at which the recursion stops splitting — decides how much it stores. On six kernels at five tolerances, thirty cells of 512 points each, one piece of arithmetic named the cheapest leaf on twenty-eight: halve the leaf while the mean rank of the blocks the halving would create is below a quarter of the leaf. It is the break-even of storing a block of side $s/2$ at rank $k$, which pays when $k < s/4$.

The rule’s weakness was named in the same essay. It reads the mean rank at half the leaf, and that rank is a property of a matrix that has been compressed. “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.”

Four ranks fed to one rule #

The rule is unchanged. What changes is the rank it is fed, which is now held fixed across the candidate leaves instead of measured at each one: start at a leaf of 64 and halve while the rank is below a quarter of the leaf. A rank of 2 or 3 stops at 8, a rank of 4 to 7 at 16, a rank of 8 to 15 at 32.

Four ranks are tried. The rule of thumb: half the number of decades of tolerance, 2 at $10^{-4}$ up to 6 at $10^{-12}$, the same for every kernel. It is not invented for the occasion. A rank that is a number of digits measured a smooth kernel block’s rank rising in a straight line at 0.55 columns a decade of accuracy, and half a rank a decade is that slope rounded to the nearest number a code would type into a default. The rule of thumb doubled for an oscillation: the same, times two for the two oscillatory kernels, $\cos(40r)/r$ and $\cos(120r)/r$. And two probes: build the matrix once, at a leaf of 16 or of 8, and read the mean rank of its compressed blocks — one compression instead of the five the rule needed. Beside them is the rule as it was, fed the measured rank at every leaf.

Each is scored twice: whether the leaf it names stores least — a tie counting as a hit — and how much its leaf stores over the least.

The kernel is what the tolerance cannot see #

The figure is the thirty cells and the four guesses, a dot where a guess named the cheapest leaf and the leaf it named instead where it did not.

The rule of thumb names the cheapest leaf on twenty-three cells. Its median cell stores exactly the least, and on twenty-five of thirty it is within five per cent. The five cells it costs more on are all the same kernel, $e^{-5r}$, whose off-diagonal blocks have rank one at every tolerance: the rule of thumb guesses two to six, names leaves of 8 and 16, and the cheapest leaf is 4. At $10^{-12}$ the leaf it names stores 33,472 numbers against 19,488, seventy-two per cent too many. A guess made from the tolerance alone assumes the kernel behaves like the smooth ones it was read from, and a kernel whose far field is separable to rounding at every tolerance does not.

The dial shows the four guesses’ costs in turn. The rule of thumb’s five expensive cells are the rank-one kernel, at 1.26, 1.26, 1.72, 1.72 and 1.72 times the least. Doubled for an oscillation the five remain and two more join them, $\cos(40r)/r$ at $10^{-4}$ and at $10^{-8}$; the doubled guess names the cheapest leaf on only eighteen cells, because on five of the oscillatory cells it names a leaf of 32 where 16 is cheapest and on two more a leaf of 16 where 8 is. Either probe puts every cell within three per cent.

The oscillation adds a rank, not a factor #

The doubling came from a prediction that arrives a decade late, which found an oscillation multiplying the largest block’s rank by exactly two — 3 and 6, 4 and 8, 5 and 10 — at any frequency. The rule does not read the largest rank. It reads the mean, and the mean behaves differently. At a leaf of 8 the mean rank of $1/r$ is 2.67, 3.67, 4.67, 5.67 and 6.67 from $10^{-4}$ to $10^{-12}$ — the rule of thumb plus two thirds of a rank, exactly, at every tolerance. $\cos(40r)/r$ runs 3.25 to 7.26, two thirds of a rank above $1/r$ and climbing at the same half a rank a decade; $\cos(120r)/r$ runs 4.08 to 8.25, about one and a half ranks above. The oscillatory kernels’ mean ranks grow with the tolerance at the smooth kernel’s rate and sit a fixed amount above it, and the amount grows with the frequency: most blocks of a partition are far from the diagonal and see few wavelengths, and only the few largest double. That is an offset, and a guess that multiplies by two turns an offset of under two ranks into an overestimate of four or five at $10^{-12}$.

Two knobs on one number found the tolerance raising every block’s rank and the leaf moving no rank at all. The kernel is a third knob on the same number, and it moves the offset: the slope, half a rank a decade, is common to every kernel except the separable one, whose slope is zero. On the oscillatory kernels the leaf turns out to move the mean rank after all, which is the next section.

Why one build is enough #

The probes work for a reason that is visible in the figure. The halving rule needs the rank at half of each candidate leaf, and on four of the six kernels that rank does not depend on the leaf it is measured at: $1/r$ has a mean rank of 4.67 at every leaf from 8 to 64, $\sqrt r$ of 4.00, $e^{-5r}$ of 1.00 everywhere, and $\log r$ moves only from 4.05 to 4.67. On those kernels one build at any leaf measures the rank every leaf would have, and holding it fixed loses nothing. That is the property the size the rank does not notice found in a single block — sampled at 32, 64, 128 and 256 points a side, a well-separated block of a smooth kernel needed five columns each time — read here across a whole partition: under strong admissibility every admissible block is about as far from its partner as it is wide, so a block of side 8 and a block of side 64 present the kernel with the same shape at a different scale, and a scale-free kernel cannot tell them apart. The two oscillatory kernels are different — $\cos(120r)/r$ rises from 4.87 at a leaf of 4 to 9.33 at 64, because a larger block spans more wavelengths — and on them a probe at one leaf reads the rank at that leaf and not at the others. An oscillation has a length of its own, the wavelength, and a kernel with a length in it is not scale-free: the kernel with nothing to compress scaled the same block up by sixteen and watched an oscillatory kernel’s rank climb from twelve to fifty-three while a smooth one held at six. But the rule only needs to be right near the leaf it stops at, and a probe at 8 or 16 is measured there.

So the probe at 8 names the cheapest leaf on twenty-nine cells and the probe at 16 on twenty-eight, the same number as the rule that builds at every leaf; the probe at 8 is right on one of the two cells the full rule missed, $\cos(120r)/r$ at $10^{-10}$, where the full rule’s measured rank at 16 was 8.12 against a threshold of 8 and the probe’s constant 6.96 is clear of it. The one cell the probe at 8 misses, $\cos(120r)/r$ at $10^{-4}$, is one whose two candidate leaves store within one and a half per cent of each other. Neither probe stores more than 2.6 per cent over the least on any cell.

Which leaf to probe at #

The probe can be built at any of the five candidate leaves, and which one matters. A probe at a small leaf measures the ranks of small blocks, which on the flat kernels are everybody’s ranks and on the oscillatory kernels are the low end of a rank that grows with the block; a probe at a large leaf measures the high end.

Built at 4 or at 8, the probe names the cheapest leaf on twenty-nine of the thirty cells, and its worst cell stores 1.5 per cent more than the least. Built at 16 it names twenty-eight and costs at most 2.6 per cent. Built at 32 or 64 it names twenty-five and twenty-four, at up to five per cent: on the oscillatory kernels a large probe reads the large blocks’ rank, which is above the rank the halving rule needs at the leaf it should stop at, so it stops a size too large. The cheap direction to probe in is down, which is also the direction in which a construction costs least to throw away.

The dashed line is what the probe’s build is worth if no rule is applied and its leaf is simply kept. A fixed leaf of 16 — a common default — is the cheapest on sixteen cells, the median cell pays nothing, and the worst pays 72 per cent, on the rank-one kernel. A fixed leaf of 8 is the cheapest on eleven and costs a median four per cent. A fixed leaf of 64 pays a median of 59 per cent and at worst nearly five times the least. Every fixed leaf is right on some kernel and wrong on another, which is the sense in which the leaf is a property of the kernel and the tolerance rather than of the implementation. The probe is the cheapest way to let an implementation find out which.

The curves at the tightest tolerance show why no fixed leaf survives. At $10^{-12}$ the rank-one kernel’s storage is least at a leaf of 4 and nearly five times that at 64, because every admissible block costs two numbers per row whatever its size and the dense blocks near the diagonal are all the leaf adds. The kernels $1/r$, $\log r$, $\sqrt r$ and $\cos(40r)/r$ all bottom out at 16; $\cos(120r)/r$ bottoms out at 32, where it stores 125,184 numbers against 127,104 at 16. Those two leaves are within one and a half per cent of each other, which is the shape of almost every miss in this essay: where the rule of thumb or a probe names the wrong leaf on a smooth or oscillatory kernel, the curve it is choosing on is nearly flat across the two leaves in question, and the miss costs little. Where the curve is steep — the rank-one kernel, whose curve rises by a factor of 1.26 to 1.75 for each doubling past its minimum — a wrong guess is expensive, and only a measurement sees it. The probe’s twenty-nine hits are not the important number. Its worst cell is: a guess that misses only where misses are cheap is a different kind of guess from one that misses where they are dear, even when the two count the same number of hits.

What this changes about choosing a leaf #

The earlier prediction that a rougher kernel wants a larger leaf was, in that essay’s words, right in sign and out by a decade of tolerance. The same thing happens here in storage: a rank guessed from the tolerance carries the kernel it was fitted to. That is fine for the smooth kernels — four of six, twenty cells of thirty, all named right — and wrong exactly where the kernel differs, by the factor of seventy-two per cent that a rank-one kernel earns over a guess of six. The doubling that was meant to correct for oscillation corrects in the wrong shape.

The probe is cheaper than it sounds. A hierarchical-matrix code builds the matrix once anyway, at some leaf, and the probe is that build read before it is kept: if its mean rank says another leaf would be cheaper, the matrix is rebuilt once. A second objective that is the first one doubled found the operation count of a hierarchical product to be exactly twice the storage at every leaf, so the leaf the probe chooses is the cheapest for the arithmetic too, and a rebuild that saves a few per cent of storage saves the same few per cent of every product after it.

The other rule, then, is the order of operations: build, read the rank, choose the leaf, rebuild if the choice moved. On these thirty cells the choice moved on the cells where the default leaf of 16 was not already the cheapest, and the rebuild brought every one within three per cent.

What thirty cells do not show #

One dimension, 512 points, strong admissibility with one separation constant, six kernels and five tolerances — the earlier essay’s grid. In two or three dimensions a cluster has many more neighbours kept dense, the break-even is no longer a quarter of the leaf, and whether the probe’s rank still stands in for the ranks at other leaves depends on whether the ranks are as flat across leaves there as they are on these one-dimensional kernels. The rule of thumb’s half a rank a decade is read off these kernels and this geometry; a different separation constant moves the offset, and a geometry setting that is a second accuracy measured how far.

Still open: a probe that reads the right block, and the oscillatory slope #

A probe of one block. Building at one leaf compresses every block. The rule needs only the rank of the blocks a halving would create, which are the ones nearest the diagonal, and compressing a handful of those — at a cost of a few blocks rather than a matrix — might read the same rank. The prediction with a sign is that the near-diagonal blocks’ rank is above the mean on the oscillatory kernels, so a near-block probe would name larger leaves there than the mean-rank probe, and be right more often.

The oscillatory offset. The two oscillatory kernels sit two thirds of a rank and about one and a half ranks above $1/r$, at frequencies of 40 and 120. If the offset grows like the logarithm of the frequency times the block size — the number of wavelengths a block spans — a guess of the form “half a rank a decade, plus a term in the wavelengths” would put the rule of thumb’s oscillatory cells right without constructing anything. The smaller cluster sets the rank found the quantity such a term would read, the product of the two clusters’ lengths over their distance in wavelengths, and under strong admissibility that product is proportional to the block’s side. The prediction is that the offset at a leaf of 8 rises by a fixed amount each time the frequency triples. Three more frequencies on the same grid would say.