Each halving reads its own width

An offset that bends twice ended on a cheaper way to choose a hierarchical matrix’s leaf. The rule from a quarter of the leaf halves the leaf, starting from 64, while the mean rank of the blocks at half the leaf is below a quarter of it, because splitting a dense block of side $s$ into two dense halves and two blocks of rank $k$ stores $s^2/2 + 2sk$ numbers against $s^2$ and pays exactly when $k < s/4$. A single compression tells the leaf fed that rule the mean rank of a single compression at a leaf of 8 instead of a compression at every candidate leaf, and on the oscillatory kernel $\cos(\kappa r)/r$ it named the cheapest leaf on thirteen cells of fifteen.

The proposal was narrower still. “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 compression at 8, because the far blocks the full compression averages in are the ones the leaf decision does not depend on.”

The prediction fails, by one cell. The way it fails says which blocks the decision does depend on, and a probe that reads those does better than anything measured before it, the full rule included.

The near blocks name twelve #

The setting is unchanged. The kernel is sampled on 512 points of the unit interval, shifted one grid spacing off the singularity, at frequencies $\kappa = 13\tfrac13$, 40, 120, 360 and 1,080 and tolerances $10^{-4}$, $10^{-8}$ and $10^{-12}$, and the partition is the strong-admissibility one from which pairs are allowed to be small. At a leaf of 8 it has 342 low-rank blocks, and 186 of them are exactly 8 wide: 124 two clusters from the diagonal and 62 three clusters from it. Those are the near blocks. The probe compresses them, takes their mean rank, and hands that number to the halving rule as the rank at every leaf.

It names the cheapest leaf on twelve cells. It wins one the full compression lost: at $\kappa = 120$ and $10^{-4}$, where the full compression names 16 for a cheapest leaf of 8, the near blocks name 8. And it loses two the full compression won, at $\kappa = 120$ and $10^{-12}$ and at $\kappa = 1{,}080$ and $10^{-8}$, besides one the full compression also lost, at $\kappa = 360$ and $10^{-8}$. Its misses store 1.5, 1.8 and 3.6 per cent more than the cheapest leaf. Every one of them has the same shape: the cheapest leaf is 32 and the probe names 16.

That shape is the clue, because a miss of 16 for 32 is a miss on one particular decision. Starting at 64 the rule asks four questions in order: halve 64 to 32 if the blocks at 32 have rank below 16; halve 32 to 16 if the blocks at 16 have rank below 8; halve 16 to 8 if those at 8 have rank below 4; halve 8 to 4 if those at 4 have rank below 2. Naming 16 where 32 is cheapest means answering the second question yes when the answer is no. The second question is about rank 8.

A block cannot hold more than its width #

An 8-wide block has rank at most 8. That is not a property of the kernel or the tolerance; it is the size of the block. So a probe made of 8-wide blocks reports a mean rank of at most 8, and reaches 8 only when every block it compresses is full. The second question halves while the rank is below 8. The near probe can answer it no only on the cells where all 186 near blocks are already full, which on these fifteen cells happens twice, at $\kappa = 360$ and 1,080 and the tightest tolerance. Everywhere else it says yes.

This figure puts every cell on one plane. Across it runs the mean rank of the 16-wide admissible blocks, the ones a leaf of 16 leaves when 32 is halved; up it runs the mean rank of the 8-wide ones. The five red points are the cells whose cheapest leaf is 32. All five lie to the right of the vertical line at 8, with 16-wide means of 8.67, 8.67, 9.33, 11.33 and 12.00, and none of the ten other cells reaches it: the largest among them is 7.67, at $\kappa = 40$ and $10^{-12}$. The line at 8 separates the cells cleanly and the decision is read off a column.

The near probe reads a row. Its values on the same five cells are 7.00, 6.67, 7.67, 8.00 and 8.00. The two at 8.00 sit on the ceiling and get the right answer by touching it. The three below are cells where the 16-wide blocks are well past the threshold while the 8-wide blocks cannot be, and those are exactly the three misses. Nothing about a frequency or a tolerance is needed to explain them: the probe was asked a question about rank 8 using blocks that can never exceed 8.

So the reason the prediction gave was wrong in a specific way. The far blocks of a compression at 8 are not irrelevant to the leaf. The wider ones among them — 16, 32, 64 and 128 wide — are the only blocks in that compression able to carry a rank of 8 or more, and the whole-compression mean got the two cells right that the near blocks missed because those wider blocks pulled it over. Its own miss runs the other way. At $\kappa = 120$ and $10^{-4}$ the 8-wide blocks have mean rank 3.67, below the 4 that halving 16 to 8 asks for, and the cheapest leaf is 8. The whole compression’s mean is 4.08, because its wider blocks are averaged in, and it says stay at 16. The near probe is right there for the reason it is wrong elsewhere.

Each width for its own halving #

Both failures are one failure. A mean over blocks of several widths answers four questions with one number, and each question is about blocks of one width. The halving from $s$ to $s/2$ creates admissible blocks $s/2$ wide, and only their rank enters its break-even. So the probe should keep the widths apart: halve 64 to 32 while the 32-wide blocks have mean rank below 16, 32 to 16 while the 16-wide ones are below 8, 16 to 8 while the 8-wide ones are below 4, and 8 to 4 while the 4-wide ones are below 2.

At $\kappa = 360$ and $10^{-8}$ the 32-wide blocks have mean rank 9.33, below 16, so 64 is halved. The 16-wide blocks are at 8.67, not below 8, so 32 stays, and 32 is the cheapest leaf. The near probe on the same cell reads the 8-wide blocks at 6.67 and halves twice. On the dial the frequency moves the 16-wide bar across its threshold between 120 and 360 while the 8-wide bar climbs toward a ceiling that is exactly where the threshold of the decision above it sits. At $\kappa = 40$ the 32-wide and 16-wide bars are under their thresholds and the 8-wide one is not, at 4.67 against 4, so the leaf stops at 16.

Read this way, one probe names the cheapest leaf on all fifteen cells. It gets the cell the near blocks missed three times, because it reads the 16-wide blocks for that decision, and the cell the whole compression missed, because it reads the 8-wide blocks alone for the decision below. That is one more than the rule with every leaf compressed, which reads the mean of a whole compression at each candidate leaf and so misses the same cell the compression at 8 does, at $\kappa = 120$ and $10^{-4}$, for the same reason. The rule was right about the break-even and wrong about which blocks to average.

The cell where the averages go wrong shows how small the margin is. The 32-wide blocks are at 5.33 and the 16-wide at 4.00, both far under their thresholds of 16 and 8. The 8-wide blocks are at 3.67 against 4, a third of a rank under, and the leaf of 8 they point to stores 1.4 per cent less than 16. A whole compression at 8 has 342 low-rank blocks, and the 156 that are wider than 8 have ranks of 4 or 6 — every 16-wide one 4, two in three of the wider ones 6; averaging them in moves 3.67 to 4.08. Moving a third of a rank to the wrong side of a threshold is enough, and nothing in the averaged number says it has happened.

Eighteen blocks stand for the partition #

Keeping the widths apart costs nothing extra; it is the same compressions grouped differently. But it also says which compressions are needed. The four questions need ranks of blocks 32, 16, 8 and 4 wide, and nothing wider. And on this grid there is a further economy, which comes from the kernel rather than from the rule.

The points are equally spaced and the kernel depends only on the distance between them, so the matrix is constant along its diagonals, a Toeplitz matrix. Two admissible blocks of the same width at the same offset from the diagonal are then the same matrix, entry for entry, and have the same rank. At a leaf of 4 the partition has 974 low-rank blocks, and those 4 to 32 wide fall into eighteen classes by width and offset: six 4-wide classes, with 632 blocks between them, at offsets of one, two and three clusters either side of the diagonal; four 8-wide classes with 186; four 16-wide with 90; four 32-wide with 42. The measurement compresses every block and checks that each class has one rank, and on every cell each does. So one block of each class is the probe. The picture shows how little of the matrix that is: the eighteen sit in the corner, the larger ones along the top and down the side, and all of them are near the diagonal, at two or three cluster widths from it. They are near blocks after all. The prediction was right to look there and wrong to look at only one width.

The leaf-4 partition matters for one more reason. A compression at a leaf of 8 contains no 4-wide blocks, so it cannot ask the last question, whether 8 should be halved to 4. On the fifteen oscillatory cells no cheapest leaf is 4 and the omission is invisible. On a smoother kernel it is not, and the classes come from the leaf-4 partition so that all four questions can be asked.

What the right blocks cost #

The work of a dense singular value decomposition of an $m \times k$ block is, to leading order, proportional to $mk\min(m, k)$, and every way of naming the leaf here is a set of such decompositions.

Compressing at every candidate leaf costs $9.33 \cdot 10^7$ in those units and names fourteen cells. One compression at a leaf of 8 costs $1.91 \cdot 10^7$ and names thirteen. The four classes of 8-wide blocks cost 2,048 and name twelve. The eighteen classes the width-matched probe needs cost 149,888 and name fifteen. That is 0.78 per cent of the compression at 8 and 0.16 per cent of the full rule, and it is the cheapest of the four ways that get the answer right more often than the near blocks do. Nine-tenths of a compression’s work, 90.4 per cent at a leaf of 8, is in the 24 blocks 64 and 128 wide, whose decompositions cost 64 and 512 times a 16-wide one and which answer none of the four questions. The kernel’s symmetry halves the count again, since a block and its transpose have one rank, so nine of the eighteen would do.

The count is of decompositions, not of a code’s wall-clock time, and it leaves out evaluating the entries, which a code that compresses from a kernel function pays block by block. Entries scale with $mk$ rather than $mk\min(m,k)$, and the eighteen blocks hold 5,472 entries against the 249,984 in a compression’s low-rank blocks, 2.2 per cent, so the ordering does not change.

Six kernels, thirty cells #

The fifteen cells are one kernel family. A single compression tells the leaf scored its probe on thirty cells, six kernels at five tolerances, and a reading that fits the oscillatory family and fails elsewhere would be a fit and not a finding.

The width-matched probe names a cheapest leaf on all thirty. The compression at 8 names twenty-nine, and its miss is the cell discussed above in another guise: $\cos(120r)/r$ at $10^{-4}$, 16 for 8, 1.4 per cent over. The exponential kernel, whose cheapest leaf is 4 at every tolerance, is the case the leaf-4 classes were for: its 4-wide blocks have rank 1, below 2, so the probe halves 8 to 4 by reading them. A compression at 8 gets the same cell only because every block of this kernel, at every width, has rank 1, so its one number happens to be the 4-wide blocks’ number too. The worst storage the probe pays over the cheapest leaf on all thirty cells is none.

Where the rule’s own reasoning pointed #

The break-even argument from a quarter of the leaf was always about one width at a time. Splitting a dense block of side $s$ pays when the blocks the split creates have rank below $s/4$; the rank in the inequality is the rank of $s/2$-wide blocks. Reading it as “the mean rank at the finer leaf” was a convenience, and on most cells the convenience is harmless because the widths in one compression have similar ranks: on $1/r$ at $10^{-8}$ the 8-, 16- and 32-wide blocks all have mean rank 4.67, because $1/r$ looks the same at every scale and a block twice as wide and twice as far is the same block magnified. It fails where the ranks spread out by width, and that is the oscillatory kernel at high frequency, where the smaller cluster sets the rank found the rank rising with the number of wavelengths a block spans. A block twice as wide spans twice as many, and at $\kappa = 1{,}080$ and $10^{-12}$ the 8-wide blocks are at 8.00 and the 16-wide ones at 12.00.

An offset that bends twice found the offset over $1/r$ flattening because the 8-wide blocks were full, and concluded that a probe which cannot see the full rank can still see which side of a threshold it is on. That conclusion holds on the cells it was drawn from and now has a limit: it can see which side of every threshold but the one equal to its own width. The offset that moved the slope found at the start of this line of measurement that a tolerance changes the slope of storage rather than lifting it. The width is the same lesson in a third variable. A single number summarising the ranks of a partition throws away the dependence on width, and the decision that needed it is the one that goes wrong.

What fifteen and thirty cells do not show #

One grid size, 512 points, equally spaced. The class economy depends on the spacing: on scattered points two blocks of the same width and offset are different matrices, and the probe would have to sample several of each and take their mean, at a cost that grows with how much the ranks within a width vary. The fifteen cells here give no measurement of that variation, because on this grid it is zero. The cost is counted in the leading term of dense decompositions, which a code using randomised or adaptive cross approximation would not pay; those methods change the constant for every probe alike and the ordering is unlikely to move, but it has not been measured. The leaf candidates are powers of two from 4 to 64, the tolerance is relative to each block’s largest singular value, and storage is counted in stored numbers rather than in the time a product takes. A margin of a third of a rank decided one cell, and a different tolerance convention could move a cell like it either way.

Still open: scattered points, and a rule that reads its own width #

Scattered points. With the points drawn at random instead of on a grid, blocks of one width and offset stop being identical. The prediction with a sign is that on 512 uniformly random points the 16-wide blocks’ ranks within one class spread by at most one, so that a probe sampling three blocks a class still names the cheapest leaf on all fifteen oscillatory cells, and that it fails first at $\kappa = 1{,}080$, where a wavelength is closest to the gaps between points.

The rule at full strength. The halving rule was derived for one dense block split once. A partition has several levels of splitting, and at the deepest one the blocks a halving creates include the 4-wide blocks one cluster from the diagonal, admissible only because a cluster of four points is narrow. The prediction is that a break-even written per width and per offset — counting the dense blocks the halving removes as well as the low-rank ones it adds — names the cheapest leaf on the thirty-cell table with a margin of at least half a rank on every cell, where the present rule decides one cell by a third.