The partition that does not move

The offset that moved the slope measured something a reader of the hierarchical-matrix literature would not expect. Accuracy is supposed to lift a storage curve and leave its growth alone — the representation is O(n log n) for any fixed tolerance, and a tighter tolerance is a larger constant. It is not: measured at seven tolerances, the strong partition adds 10.9 numbers per unknown per doubling at two digits and 36.5 at twelve, so the growth rate more than triples and the ten decades cost 33 per cent more storage at 64 unknowns and 118 per cent at 512.

The essay reported the slope moving and did not say what moves it. There are exactly two candidates and they are easy to separate, which is what this essay does.

Two candidates #

The kernel with nothing to compress is the case where the whole construction fails, and it fails by the first mechanism below. A hierarchical representation’s storage is a sum over blocks. A dense block of m by k costs mk; a low-rank block of rank r costs r(m + k). So the total is decided by which blocks are which, how many there are, and what ranks the low-rank ones have.

A tighter tolerance could therefore raise the storage two ways. It could move blocks from the low-rank list to the dense one — a block whose singular values do not fall fast enough to be worth compressing at 10⁻¹² might have been worth compressing at 10⁻² — which would raise the count of dense blocks and with it the storage. Or it could leave every block where it is and raise the ranks.

Those are different mechanisms with different consequences. The first would mean the representation degenerates toward a dense matrix as the tolerance tightens, and the growth rate rising would be a symptom of that degeneration. The second would mean the structure is fixed and only its contents get longer.

The partition is decided before any tolerance is applied #

The measurement is unambiguous. At n = 512, at tolerances of 10⁻², 10⁻⁴, 10⁻⁶, 10⁻⁸, 10⁻¹⁰ and 10⁻¹²:

Identically, at every one. Not approximately and not within a block or two.

The reason is in the construction and is worth stating because it makes the result a check on the implementation rather than a discovery about matrices. The partition comes from partition(tree, {admissibility}), which walks the cluster tree and marks a block admissible when the two clusters are far enough apart relative to their diameters — a purely geometric test on the points, run before the matrix is looked at. compress(A, blocks, eps) then takes that partition and decides a rank for each admissible block from its singular values.

So the tolerance cannot move the partition, because the partition has already happened. A block marked admissible is compressed to whatever rank the tolerance demands, up to its full rank; it is never returned to the dense list.

That is a design decision rather than a law, and it is the standard one: geometry decides what may be low rank and the tolerance decides how low. An adaptive scheme that refused to compress a block whose rank came out near full would behave differently, and the first candidate would then be live.

Which pairs are allowed to be small is the essay about that decision — what the admissibility test is and what it costs — and reading it beside this measurement makes the division of labour explicit. The test decides the structure and knows nothing about accuracy; the compression decides the contents and knows nothing about geometry. Two stages, two inputs, and the storage curve is a product of what each supplies.

And the rank rises by one per two decades #

The other candidate is what moves, and it moves with a regularity that is the essay’s second finding.

The mean rank of the 156 low-rank blocks reads 1.67, 2.67, 3.67, 4.67, 5.67 and 6.67 across the six tolerances. Exactly one more per two decades of accuracy, to the digit, five times running.

That is not a coincidence of this kernel; it is what a geometric decay in a block’s singular values produces. If $\sigma_j/\sigma_1$ falls by a factor $c$ per index, the number of singular values above a threshold $\varepsilon$ is $\log\varepsilon / \log c$, so the rank is linear in the logarithm of the tolerance — which is linear in the number of digits. Two decades per unit of rank means c ≈ 10⁻², a hundredfold decay per singular value, which is fast and is what a smooth kernel on well-separated clusters gives.

The maximum rank rises the same way, 2 through 7, so the distribution is moving rigidly rather than spreading.

A rank that is a number of digits established that relation for a single block and named it in its title. What this essay adds is that the relation survives averaging over a hundred and fifty-six blocks of different sizes and separations, with the mean rank as regular as any one block’s — which is not obvious, since blocks at different levels of the tree have different decay rates and a mean of things with different slopes need not have a slope at all.

That it does is a statement about the partition. The admissibility test admits a block when its clusters are separated relative to their diameters, and that ratio is what sets the decay rate, so a partition built to one separation threshold gives blocks with similar decay — and the mean inherits their common step.

Which makes the slope a straight line in the rank #

Put the two together and the slope is predictable. The storage is a sum of r(m + k) over a fixed set of blocks, so at fixed geometry it is linear in the rank — and if the mean rank is linear in the digits, so is the slope.

Fitted through the six points, the slope is 5.11 numbers per unknown per doubling per unit of mean rank, with an intercept of 2.36 and a worst residual of 0.03 over the six. Three decimal places of agreement between a mechanism and six measurements is as close to an identity as a fitted line gets.

The intercept is the dense blocks, which cost the same at every tolerance and contribute a slope of their own: 94 dense blocks of 16 by 16 at n = 512 is 47 numbers per unknown, and that quantity’s own growth with n is what 2.36 is.

The offset that moved the slope is the measurement being decomposed and a block nobody can call sparse is where the ranks it depends on were first measured. So that measurement’s headline — 10.9 at two digits and 36.5 at twelve — decomposes exactly: 5.11 × 1.67 + 2.36 = 10.9, and 5.11 × 6.67 + 2.36 = 36.4 against a measured 36.5.

Why a fixed partition is the right design anyway #

The measurement establishes that the partition does not respond to the tolerance, and it is worth saying that this is a good property rather than a limitation the next version would fix.

A partition that re-marked blocks would have to decide, per block, whether the rank the tolerance demands is high enough that storing the block densely is cheaper. The crossover is at rank r = mk/(m + k), which for a square block is half its side — so the rule would be “compress unless the rank exceeds half the block’s side”, and it would fire only on blocks whose singular values barely decay. The measurement says the maximum rank at twelve digits is 7 on blocks whose smallest side is 16, so the rule would never fire on this kernel at any tolerance the arithmetic supports.

It would fire on a kernel with no decay — the kernel with nothing to compress is that case measured — and there the whole representation is the wrong one and a rule that noticed would be reporting a failure rather than optimising. So an adaptive partition is a diagnostic rather than a saving, which is a reasonable thing for an implementation not to have and an unreasonable thing for a reader to assume it does.

The design’s real cost is elsewhere and this measurement makes it visible: because the partition is fixed, the dense blocks’ contribution is a constant that no tolerance can reduce. At two digits they are 47 of the 78 numbers per unknown at n = 512 — sixty per cent of the storage — and nothing about asking for fewer digits touches them. That is what the intercept of 2.36 is, and it is why the storage curve at two digits is not six times lower than the one at twelve.

What that means the growth rate actually is #

The clean statement the earlier measurement could not make is available now.

Numbers stored per unknown grows by about 2.55 per doubling per decade of accuracy, plus 2.4 per doubling for the dense part — because the rank is half a unit per decade and the slope is 5.11 per unit.

That is a growth rate that depends on the accuracy, which is what the earlier measurement found and is what the standard O(n log n) statement hides. The standard statement is not wrong: at any fixed tolerance the storage is O(n log n) and the rank is a constant. What it does not say is that the constant multiplying the logarithm is proportional to the number of digits, so a representation asked for twelve digits has six times the logarithmic term of one asked for two.

A reader who wants one sentence: the tolerance does not change the shape of the curve, it multiplies the part of it that grows.

What must fail for any of this to be wrong #

Four claims and a refusal. That the block count is the same at every tolerance, checked at all six. That the split between low-rank and dense is too, which is the sharper version of the first. That the mean rank rises by one per two decades, checked between every consecutive pair with a tolerance of 0.1. And that the slope is linear in the mean rank with a worst residual below 0.3, at a gradient between 4 and 7.

The refusal is fed the claim that the dense count rises with the tolerance.

The mean rank and the slope are computed from different objects — the rank from the representation at one size, the slope from a four-point regression across sizes — so the line through them is a relationship between two measurements rather than an identity rearranged.

The two routes to the same number #

The slope can be got two ways and the agreement between them is what makes the decomposition a measurement rather than a rearrangement.

The first route is the regression: fit numbers-per-unknown against log₂ n over four sizes, and read the gradient. That is what the earlier measurement reported and it knows nothing about ranks or blocks.

The second is the construction: at n = 512 the representation holds 156 low-rank blocks and 94 dense ones, the low-rank ones store rank × (rows + columns), and doubling n adds a level to the cluster tree with its own low-rank blocks. Counting those blocks and multiplying by the mean rank gives a slope directly, and it is the quantity 5.11 × mean rank + 2.36 reproduces.

The two agree to a worst residual of 0.03 across six tolerances spanning ten decades. Neither is derived from the other — one is a fit across sizes at fixed tolerance, the other a count at fixed size across tolerances — so the agreement is a check that the mechanism proposed is the operative one and not merely consistent with the numbers.

What a fixed rank would have looked like #

It is worth asking what the measurement would have shown if the other candidate had been the operative one, because the two are distinguishable in more than the block counts.

If the tolerance moved blocks from the low-rank list to the dense one, the storage would rise by whole blocks rather than by ranks — a dense 16 by 16 block costs 256 numbers where a rank-5 one costs 160, so each re-marked block would add 96 in a jump. The storage against tolerance would be a staircase rather than a line, with a step at each tolerance that pushed one more block over, and the mean rank of what remained would fall as the hardest blocks left the list.

Neither happens. The storage per unknown reads 78, 96, 114, 133, 151 and 170 at the six tolerances at n = 512 — even steps of about 18, which is 156 low-rank blocks each gaining one rank on sides summing to about 18 numbers — and the mean rank rises monotonically. Both signatures point the same way.

That is the value of naming both candidates before measuring. A measurement that only reported the block counts would leave a reader wondering whether the storage rose for some third reason; one that reports the counts, the ranks and the shape of the storage curve has three independent things agreeing.

What this does not settle #

One kernel, one point distribution, one admissibility rule, one leaf size. The 5.11 is a property of this partition: it is the number of low-rank blocks per unknown per level times the average of m + k over them, and both are geometric.

Four sizes for the regression, 64 to 512, so the slope is a chord rather than a derivative. The exponents between consecutive sizes fall towards one and never arrive, which is what the earlier measurement reported and is why a chord over three doublings is the honest instrument.

The rank is the number of singular values above ε times the largest, per block, which is a relative criterion inside each block. A rank that is a number of digits is where the relation between the two is measured directly: the assembled error is about a fortieth of ε at every accuracy, so the digits requested and the digits delivered differ by a factor that the rank measurement inherits.

And the partition’s fixity is a property of this implementation’s design. A scheme that recompressed or re-marked blocks would behave differently and the first candidate would be live again.

What the earlier measurement would have found sooner #

One methodological note, because it is the second time this phase has run into the same thing.

The earlier measurement measured a slope at seven tolerances and reported that it moved. Everything needed to say why was already computed on every one of those runs: building a representation returns the block counts and the rank of every low-rank block, and the storage sweep returns the largest rank per size. The quantities were in the return values and were not looked at, because the figure was about a curve and the curve is what the essay was about.

That is the ordinary way a mechanism stays unmeasured. A sweep is written to produce one number, the number is interesting, and the intermediate quantities that would explain it are discarded by the plot rather than by the method. The repair here was four lines — sum the ranks, count the blocks, fit a line — and it turned “the growth rate more than triples” into “the rank rises one per two decades and the slope is 5.11 per unit of it”.

The general form is worth carrying into the next sweep is written next: when a measurement finds a rate moving, the quantities that could move it are almost always already in hand, and the question of which one it is is usually a fit rather than an experiment.

Still open: the decay constant, the geometry, and the other knob #

Whether the two-decades-per-rank is the kernel’s. The step of one rank per two decades implies a hundredfold decay per singular value in the admissible blocks. That number should be readable off the blocks directly and should change with the separation ratio η, which decides how far apart two clusters must be to be admissible. Measuring the decay and predicting the step from it is the two-routes check this essay checks the consequence of without checking the cause.

The same decomposition for the weak partition. The weak rule admits more blocks and gives them higher ranks, so both factors move together and the slope’s dependence on the rank might not be the same 5.11. It is the same sweep with one argument changed.

And the leaf size, which is the other knob on the same number. The tolerance raises every rank and leaves the partition alone. The leaf size does the opposite — it changes how many blocks there are and does not touch a single rank — so the two knobs act on the same product from opposite sides, and whether they trade is the next essay.