The size the rank does not notice

A null result is the hardest kind of measurement to publish honestly, because a quantity that does not move is indistinguishable from an experiment that cannot move it. This essay is a null result and its control, and the control is on the same figure for exactly that reason.

The measurement #

Two intervals, [0, 1] and [2, 3], the kernel 1/r, and the block between them sampled at 32, 64, 128 and 256 points a side. Count the singular values above 10⁻⁸ of the largest:

Four sizes, a factor of eight in each direction, a factor of sixty-four in the number of entries, and one number.

The storage that follows is the reason it matters. Two factors of n × 5 is 10n numbers, against n² entries: 320 against 1,024 at the smallest size and 2,560 against 65,536 at the largest. The saving is a factor of 3.2 at n = 32 and a factor of 26 at n = 256, and it keeps improving, because the numerator grows linearly and the denominator does not.

What makes it a measurement #

The same figure carries a second row. Take the touching pair — [0, 1] against [1, 2], two intervals that share an endpoint — with the same kernel, the same four sizes, and the same 10⁻⁸:

The second column climbs by about one and a third per doubling, which is a logarithm. It is not dramatic — 13 out of 256 is still a compressible block — and it is unmistakably not flat.

So the experiment is capable of detecting growth. It detects growth in the second column, on the same kernel, at the same tolerance, in the same code, differing only in where the two intervals sit. The first column’s flatness is therefore a property of the geometry and not of the measurement.

Why the first row is flat #

The rank belongs to the function, not to the samples of it.

The expansion in the first essay of this field approximates the kernel 1/(x − y) by a sum of p + 1 products of a function of x with a function of y, on the whole of the two intervals. It is an approximation of the kernel as a function on a rectangle, and its accuracy depends on the rectangle — which is to say on q, the separation ratio — and not on how many points are laid down inside it.

Sampling that approximation at n points a side produces a rank p + 1 matrix, whatever n is. Sampling it at twice as many points produces a bigger matrix of the same rank, with the same relative error. The block gets larger and no more complicated.

That is a completely ordinary statement about approximation and it has an extraordinary consequence, which is the reason this field exists: the cost of storing an off-diagonal interaction does not grow when the problem is refined. A finer mesh costs more unknowns, more blocks and more rows in each block, but not more columns in any of them.

Why the second row is not #

The touching pair fails the expansion’s condition exactly. q = (½ + ½)/1 = 1, the geometric series does not converge, and there is no separable approximation of the kernel on that rectangle at all — because the rectangle contains the singularity, where 1/(x − y) is unbounded.

What the block has instead is a nearly singular corner. The entries near the shared endpoint are large and the ones far from it are small, and the number of columns needed depends on how finely the corner is resolved. Halving the mesh brings the two closest points twice as close, doubles the largest entry, and adds a column.

That is the logarithm. It is a very slow growth and it is unbounded, and the difference between slow and bounded is the difference between a format whose cost per unknown is a constant and a format whose cost per unknown creeps up forever.

What a partition does about it #

There are two possible responses to a block whose rank climbs and both are used.

The first is to compress it anyway. The rank is still small, the growth is slow, and the simplicity of a partition that asks no questions is worth something. That is weak admissibility, it is what the HODLR format does, and the sixth essay in this field measures what it costs.

The second is to refuse. A pair of clusters that touches is subdivided into four pairs of half-size clusters, of which three are now separated and one still touches; recurse, and the touching pairs shrink until they are small enough to store densely. That is strong admissibility, it is what an H-matrix does, and the fifth essay is about the test that decides it.

Neither is obviously right, which is why both are measured rather than one of them recommended. What this essay establishes is the quantity the choice is about: not whether a touching block is compressible — it is — but whether its cost is a function of the discretisation, which is a question a code has to answer before it has discretised anything.

The arithmetic of the saving, since a ratio is not a number #

It is worth doing the counting explicitly, because a factor of twenty-six is the kind of claim that sounds like a result and is really an arithmetic identity waiting to be checked.

A block of n × n entries stored as two factors of rank k costs 2nk numbers. The ratio to n² is therefore 2k/n, and everything about whether a hierarchical format is worth having is in that fraction. At k = 5:

At the smallest size the saving is a factor of three, which is not enough to justify a format. At the largest it is twenty-six. And the reason it improves is entirely the flat column: if k grew like n^½ the ratio would be 2/√n and the saving would still improve but far more slowly, and if k grew like n there would be no saving at any size at all.

So the null result is not decoration on a storage claim; it is the storage claim. Everything else in this field — the partition, the recursion, the solve — is machinery for applying it to a whole matrix rather than to one block, and none of the machinery would be worth writing if the first column of the first table were not constant.

The second table’s touching column is the same arithmetic with k growing like log n, giving a ratio of 2 log n / n. That still goes to zero, which is why weak admissibility works at all; it goes to zero more slowly, which is what the sixth essay measures.

The claim in the title is a claim about a row of a table being constant, and a row of a table can be constant by accident at one tolerance. It is not constant by accident at five.

Five tolerances, and the admissible row is constant in n at every one of them — 9, 9, 9, 9 at 10⁻¹⁴; 6, 6, 6, 6 at 10⁻¹⁰; 5, 5, 5, 5 at 10⁻⁸; 4, 4, 4, 4 at 10⁻⁶; 2, 2, 2, 2 at 10⁻². The touching row climbs at every one of them instead, from 14 to 21, 11 to 16, 9 to 13, 8 to 11 and 3 to 5 across the same eight-fold range of n.

And the penalty for the weaker test is nearly independent of the tolerance. Dividing the two rows at the largest size gives 2.33, 2.67, 2.60, 2.75 and 2.50 — a factor of about two and a half, whether the tolerance is two digits or fourteen. At the smallest size the same ratio is 1.56, 1.83, 1.80, 2.00 and 1.50, so the factor grows with n and not with ε.

That separation is the useful form of the result. What the tolerance decides is the height of both rows; what the size decides is the gap between them. A caller choosing an admissibility test is choosing whether the rank grows with the problem, and the tolerance they pick has almost nothing to do with how much that choice is worth.

The admissible row also has a rate. It reads 2, 4, 5, 6 and 9 at 10⁻², 10⁻⁶, 10⁻⁸, 10⁻¹⁰ and 10⁻¹⁴ — about one more rank for every two decades of tolerance, exact at the first four and one rank high at the tightest. So the storage a hierarchical representation needs grows like the logarithm of the accuracy asked for and not at all with the size, which is the whole economic case for the format.

Where the site has met this shape before #

A quantity that does not notice the discretisation is a familiar thing here and it has always been good news.

A rate that does not notice the size is multigrid’s central claim: the convergence factor of a V-cycle is a constant, so the number of iterations does not grow when the mesh is refined, and the whole method exists because of it. The dimension does not appear is the randomised field’s version: the number of samples a sketch needs depends on the target rank and on a failure probability, and not on how many columns the matrix has.

This is the third. In each case the mechanism is the same in outline — the quantity is a property of the continuous problem rather than of its discretisation — and in each case the consequence is that a cost which looks as though it must grow does not.

It is worth saying which of the three is weakest. Multigrid’s constant is proved and measured; sketching’s is proved with a probability attached; this one is measured over a factor of eight and explained by an argument about a convergent expansion. A factor of eight is not an asymptote, and the honest form of the claim is that the rank does not move over the range this site can afford to compute, for a reason that says it should not move at any range.

The two axes it does move on #

The touching row shows that the experiment can detect growth. It is a single alternative geometry, and a null result deserves a better control than one, so here are the two sweeps that vary the quantities the argument says the rank actually depends on.

Separation. The same block — [0, 1] against [gap, gap + 1] — at a fixed n = 128, counted at the same 10⁻⁸. At gap 1, which is the touching case, the count is 12. At 1.25 it is 7, at 1.5 it is 6, at 2 — the geometry of the first table — it is 5, at 3 it is 4, at 8 it is 3, and at 16 it is still 3. The separation ratio q runs from 1 down to 0.06 and the count runs from 12 down to 3.

Tolerance. The same block at gap 2, counted at successively finer cuts: 2 columns at 10⁻², 3 at 10⁻⁴, 4 at 10⁻⁶, 5 at 10⁻⁸, 6 at 10⁻¹⁰, 7 at 10⁻¹². Exactly one column per two decades, with no exception across the range.

Put beside the first table those two are the whole argument in three lines. A factor of eight in the discretisation moves the count by zero. A factor of sixteen in the separation moves it by nine. A factor of 10¹⁰ in the tolerance moves it by five. The instrument responds to both of the quantities the theory says it should and to neither of the ones it says it should not, which is a stronger statement than a single control can make.

What the bound is worth, which is less than it looks #

The tolerance sweep also prices the expansion the whole argument rests on, and the number is not flattering.

A separable expansion of 1/r on a pair of clusters with separation ratio q converges geometrically: the error after p terms is O(qᵖ). So at q = 0.5 and a target of 10⁻⁸ the bound says p ≈ 8·ln 10 / ln 2 ≈ 27 terms. The block needs 5.

The bound over-predicts by more than a factor of five, and it does so in the direction that matters: anybody sizing an allocation, choosing a leaf size, or deciding whether a format is worth building from the estimate alone would conclude that a 32 × 32 block compresses to 27 columns out of 32 and is not worth compressing at all. On this kernel it compresses to five.

The gap is not a defect in the bound. The expansion is one particular separable approximation, chosen because its convergence is provable; the singular values are the best separable approximation at every rank, and being better than a specific construction is what optimality means. What the measurement adds is the size of the difference, and the size is the thing an estimate is used for.

That leaves the argument doing exactly the work it should and no more. The expansion explains the flatness and does not predict the count. It says the rank is a property of q and ε and not of n, which is the null result and the reason the format exists; the number of columns is a measurement, and it would be a different number for a different kernel with the same q. This collection’s usual formula for that split is a bound beside the quantity it bounds, and the usual finding is that the two are the same shape and a long way apart.

It also explains why the touching row is worth having twice over. At q = 1 the bound does not merely over-predict, it says nothing at all — qᵖ = 1 for every p — and the measured 9, 11, 12, 13 is the only information available about that block. A bound that is loose where it applies and silent where it does not is a poor instrument for deciding a partition, which is the argument for making the admissibility test a measurement of the geometry rather than a threshold on an estimate.

What it would take to break it #

Naming the conditions is more useful than repeating the result, and there are three.

A kernel with no convergent separable expansion. The next essay is this one, in full: an oscillatory kernel on identical geometry, whose rank grows with the size of the picture at a fixed wavelength and has no size at which it stops.

Points that are not where the geometry says they are. The tree that produces the two clusters is built from the points, and if the indices are numbered so that a cluster of indices is not a cluster of points, the block between two nodes of the tree is not the block between two intervals and none of this applies. That is the seventh essay, and the measurement in it is that one permutation takes the storage from 27,008 numbers to 118,208 without moving anything a norm can see.

And a tolerance below the working precision, where the count stops selecting columns and starts counting rounding error. The 5 becomes a 9 at 10⁻¹⁴ partly for that reason, as the previous essay records.

Outside those three the flat row is what happens, and it is the reason the whole format is worth building.

The measurement nobody can take #

There is a limit on all of this that is easy to state and impossible to remove, and stating it is the price of publishing a null result.

The four sizes above span a factor of eight. They stop at 256 because the reference this measurement is against is a dense singular value decomposition of the block, which is cubic, and because every other figure in this field needs to be recomputed every time this site is built. A claim about an asymptote is a claim about behaviour past every size anyone can compute, and no amount of computing reaches it.

What can be said is what the argument says. The rank of the continuous operator’s approximation is p + 1 for a p that depends on q and on ε and on nothing else, and every matrix in the first column is a sampling of that same approximation. If the column were going to bend it would have to bend because the sampling started to matter, and the mechanism by which sampling matters is visible in the second column — where it does matter, and where the bending is exactly what is seen.

So the honest form is: flat over a factor of eight, with a mechanism that says it stays flat, and a control on the same figure showing what not-flat looks like in this experiment. That is three things, and a table with one of them would be worth much less than a table with all three.

This is the same care the multigrid essays take with their own constant, and for the same reason. A convergence factor measured on grids from 15 to 127 is not a proof of mesh independence; it is a measurement consistent with one, taken alongside a closed form that predicts it. Neither field can do better and both can say clearly which of the two they are doing.

The refusal #

The claim under test is one nobody states and everybody assumes: that a finer discretisation costs more to store, in proportion.

It is refused by the first row of the table, and the assertion that carries the refusal is deliberately the weakest possible version — not that the rank is bounded, not that it is asymptotically constant, just that the count at 256 points exceeds the count at 32. It is fed 5 and 5, and it fails.

Fed the second row it would pass, and that is the point of having both. An assertion that cannot distinguish the two rows is not evidence about either.