An offset that bends twice

One build tells the leaf settled what a hierarchical-matrix code needs to know to choose its leaf. The rule from a quarter of the leaf — halve the leaf while the mean rank at half the leaf is below a quarter of it — names the cheapest leaf on almost every one of thirty cells, six kernels at five tolerances, but it reads ranks that exist only after the matrix has been compressed at every candidate leaf. Fed instead the mean rank of a single build at a leaf of 8, it named the cheapest leaf on twenty-nine cells of thirty. Fed a rank guessed from the tolerance alone, one rank per two decades, it named twenty-three and was blind to the kernel. And doubling the guess for the two oscillatory kernels made it worse, because an oscillation does not double the rank. It adds to it.

Its last section proposed to measure what the oscillation adds and turn it into a formula. “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 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.”

Three more frequencies say no. The offset rises slowly, then by about a rank a tripling, then slowly again, and the reason for each bend is a different property of the same blocks.

Five frequencies a tripling apart #

The setting is the earlier essays’, built on the partition which pairs are allowed to be small introduced: four numbers per pair of clusters decide whether their block may be compressed, and no entry of the matrix is read to decide it. The kernel $\cos(\kappa r)/r$ is sampled on 512 points of the unit interval, shifted by one grid spacing off the singularity, and represented as a hierarchical matrix with strong admissibility: a pair of clusters is stored as two thin factors when they are far enough apart relative to their size, and densely otherwise. Each admissible block keeps as many singular values as are above the tolerance times its largest, so its rank is a number of digits as much as a property of the kernel, the dependence a rank that is a number of digits measured on a smooth kernel at about half a column a decade. The partition is geometric and the same at every frequency: at a leaf of 8 it has 532 blocks, 342 of them low-rank and 186 of those exactly 8 wide.

The frequencies are $\kappa = 13\tfrac13$, 40, 120, 360 and 1,080 — the earlier essay’s two, one below them and two above, each three times the last. The offset is the mean rank of the low-rank blocks at a leaf of 8, less the same mean for $1/r$ at the same tolerance. It is measured at five tolerances, from $10^{-4}$ to $10^{-12}$.

At a tolerance of $10^{-8}$ the offsets are 0.30, 0.65, 1.81, 3.04 and 3.76. A fixed step a tripling would draw a straight line on that axis. The measured curve starts below the line, rises above it, and flattens. The dial shows the same shape at every tolerance: at $10^{-4}$ the offsets are 0.35, 0.58, 1.41, 2.30 and 2.67; at $10^{-12}$, 0.21, 0.59, 1.58, 3.24 and 3.42.

The steps, and how far they are from fixed #

The figure above reduces the curves to their steps. Averaged over the five tolerances, the offset rises by 0.28 of a rank from $13\tfrac13$ to 40, 0.95 from 40 to 120, 1.39 from 120 to 360, and 0.38 from 360 to 1,080. The largest step is five times the smallest, and the ranges at the separate tolerances do not overlap between the middle two steps and the outer two. There is no fixed amount a tripling for a formula to add.

The first bend has an explanation the earlier essays already hold. At $\kappa = 13\tfrac13$ a wavelength is about half the interval, and the 8-wide blocks span a thirtieth of a wavelength; the kernel inside them is essentially $1/r$ with a slowly varying factor, and the oscillation adds almost nothing. The added rank starts to count when a block spans a fair fraction of a wavelength, and the kernel with nothing to compress measured what happens after that: at a fixed geometry the oscillatory rank grows with the number of wavelengths across the block, without limit, roughly in proportion once there are several. On the frequency axis that is growth faster than logarithmic, which is what the middle steps show. A guess that adds a fixed amount per tripling would be calibrated on the middle of the curve and wrong at both ends.

An offset in ranks, not in digits #

The offset has one property the proposal assumed and the measurement confirms: it is added, not multiplied, and below the point where blocks fill it barely depends on the tolerance. At $\kappa = 40$ it is 0.58, 0.58, 0.65, 0.63 and 0.59 across tolerances from $10^{-4}$ to $10^{-12}$ — the same two thirds of a rank whether the matrix is asked for four digits or twelve — while $1/r$’s own mean rank at a leaf of 8 climbs from 2.67 to 6.67 over the same range, one rank for every two decades. At $\kappa = 120$ the offset wanders between 1.30 and 1.81 with no trend. That is what one build tells the leaf meant by an oscillation adding a rank rather than a factor: the oscillation contributes a fixed number of singular values above every tolerance, the ones that carry its wavelengths, and the tolerance then decides how many of the smooth part’s decaying singular values come along.

From $\kappa = 360$ on that stops being true. The offset at 360 rises from 2.30 at $10^{-4}$ to 3.24 at $10^{-12}$, and at 1,080 from 2.67 to 3.85 and back to 3.42. Once a block spans several wavelengths, the oscillatory part’s own singular values decay instead of stopping, so a tighter tolerance keeps more of them — and the smallest blocks then reach their cap, which takes some of the growth away again. A correction term would have to be a function of the frequency and the tolerance from there on, which is one more reason a fixed step was never going to describe it. A geometry setting that is a second accuracy found the admissibility constant moving both the number of blocks and their ranks; the frequency here moves the ranks alone, and moves them in a way that depends on the digits asked for only once the blocks are long enough to see the oscillation as more than a phase.

The smallest blocks fill first #

The last step is small for a reason that has nothing to do with the kernel getting easier.

An 8-wide block cannot have a rank above 8. At the tightest tolerance the 186 such blocks have mean ranks of 6.67, 6.67, 7.00, 8.00 and 8.00 across the five frequencies: from $\kappa = 360$ on every one of them is at full rank, where at 120 none is. The larger blocks keep climbing — 7.13, 7.96, 9.74, 12.18 and 12.56 — but they are 156 of the 342, and the mean over all of them is pulled flat by the 186 that have nowhere to go. At $10^{-10}$ the 8-wide blocks fill between 360 and 1,080, 124 of them at 360 and all 186 at 1,080; at $10^{-8}$, 124 of them fill at 1,080.

At the two loosest tolerances no 8-wide block is full even at 1,080, and the last step is still small — zero at $10^{-6}$, where the offsets at 360 and 1,080 are both 2.94. Full blocks do not explain that. What is left at those tolerances is the grid. At $\kappa = 1{,}080$ a wavelength is under three grid spacings, so the sampled kernel is close to the shortest oscillation 512 points can carry, and blocks of a given number of points can hold only so many independent oscillations however high the frequency is set. Whether that is the whole of it is a question for a finer grid, which this one cannot answer.

The cheapest leaf moves with the frequency #

What a formula for the offset was for is the leaf. A higher frequency raises the ranks, which raises the cost of a large leaf’s off-diagonal blocks relative to its dense ones, and the cheapest leaf should move up.

It does. At $10^{-8}$ the cheapest leaf is 16 for the three lower frequencies and 32 for the two higher ones; at $10^{-12}$ it moves from 16 to 32 already at 120; at $10^{-4}$ it is 8 below 360 and 16 from there. The curves are shallow near their minimum — at $\kappa = 360$ and $10^{-8}$ a leaf of 16 costs 1.8 per cent more than 32 — so a guess that is one halving out is a guess that costs a few per cent, not a factor.

One build still tells the leaf #

The rule of thumb — half a rank a decade, the same at every frequency — names the cheapest leaf on all six cells at the two lower frequencies, on two of three at 120, and on none of the six at 360 and 1,080. Its misses store 1.5 to 8.6 per cent too much, and the miss grows with the frequency, because the thumb’s leaf stays where it was while the cheapest leaf moves. The probe — the mean rank of one build at a leaf of 8 — names the cheapest leaf on thirteen cells of fifteen. Its two misses are at $\kappa = 120$ and $10^{-4}$, where it names 16 for a cheapest leaf of 8 and stores 1.4 per cent more, and at $\kappa = 360$ and $10^{-8}$, where it names 16 for 32 and stores 1.8 per cent more.

That last result answers a worry the saturation raises. At the high frequencies and tight tolerances the probe’s own blocks are full: its mean rank at a leaf of 8 cannot grow past what the 8-wide blocks allow, so it understates how much the kernel’s rank is rising. It names the cheapest leaf anyway, on five of the six cells at 360 and 1,080, because the halving rule needs only to know whether the rank at half a leaf is above or below a quarter of the leaf, and a saturated probe at 8 is already well above a quarter of 16. A probe that cannot see the full rank can still see which side of a threshold it is on.

Put in terms of what a code pays, the comparison is this. The halving rule fed every leaf’s ranks needs five compressions, one at each candidate leaf; the probe needs one, at the smallest leaf, which is also the cheapest of the five to compress because its blocks are smallest; the thumb needs none. On these fifteen cells the thumb’s worst choice stores 8.6 per cent too much and the probe’s 1.8. For a matrix that is compressed once and multiplied a thousand times, the probe’s single build is repaid by the first few products that the thumb’s extra storage would have slowed; for one compressed once and used once, the thumb’s misses may be the cheaper mistake. The measurement prices both and does not choose.

What a formula would have needed #

A term that corrects the thumb has to know the offset at the frequency and tolerance in hand. The measurement shows the offset is not a function of the frequency alone: it depends on how many wavelengths the blocks span, on whether the smallest blocks are full at that tolerance, and on how close the frequency is to what the grid can carry. Each of those is computable — the first from the geometry, the second from the tolerance and the leaf, the third from the grid — but together they are a model of the compression, and the cheapest way to evaluate a model of the compression is to compress a little. One build at a leaf of 8 is that evaluation. The smaller cluster sets the rank found the quantity a formula would read — the product of the two clusters’ lengths over their distance, in wavelengths — and it is the right quantity for one block; summed over a partition, with the small blocks’ caps, it is the probe again.

The offset that moved the slope found, at the start of this line of measurement, that a tolerance’s effect on storage is not a constant lift but a change of slope. The frequency is the same lesson in a second variable: its effect is not a constant added rank but one that depends on where the blocks sit relative to a wavelength, and on whether they have room left. So the earlier essay’s conclusion stands, with its reason sharpened. A guess from the tolerance is blind to the kernel, and no single correction term restores its sight, because what the kernel adds is not one number. One compression at the smallest leaf reads what the kernel adds, caps and all, at no more than its own cost.

What fifteen cells do not show #

One kernel family, one grid, one admissibility rule, five frequencies and three tolerances for the leaf. A grid of 1,024 points would put a wavelength at $\kappa = 1{,}080$ at six spacings instead of three and would say whether the flat last step at loose tolerances is the grid’s; the dense reference this measurement needs is not affordable there. The leaf candidates are powers of two from 4 to 64, so a cheapest leaf between 16 and 32 is reported as one of them. The tolerance is relative to each block’s largest singular value, which is what the earlier essays used and not what every code does; an absolute tolerance would make the far blocks’ ranks smaller and could move the cheapest leaf down. The probe is scored against the cheapest of the five leaves, not against a leaf chosen continuously, and the storage it is scored on is the count of stored numbers, not the time a product takes, which a real code would also weigh.

Still open: a finer grid, and a probe that reads the near blocks #

A finer grid. At loose tolerances the offset stops growing between 360 and 1,080 with no block at full rank. The prediction with a sign is that on a grid of 1,024 points the step from 360 to 1,080 at $10^{-6}$ is at least as large as the step from 120 to 360 — that the flat step on this grid is the grid’s resolution, not the kernel’s — and that at $\kappa = 3{,}240$ on the finer grid it flattens again.

A probe of the blocks a halving creates. The earlier essay’s first question stands. The halving rule compares the rank at half a leaf with a quarter of the leaf; the blocks that comparison is about are the ones a halving creates, nearest the diagonal. A probe that compresses only a handful of those, at a leaf of 8, costs a few blocks instead of a matrix. The prediction is that it names the cheapest leaf on at least as many of these fifteen cells as the full build at 8, because the far blocks the full build averages in are the ones the leaf decision does not depend on.