The cliff behind the count

The sparsity field’s reading of the fill is an integer. The essay that counted it takes the Schur complement nested dissection leaves on a separator, bisects the separator, and asks how many columns the block between the two halves needs at eight digits. The answer is 4 at a separator of eleven, 5 at fifteen, 6 at twenty-three — and 6 again at thirty-one, which is the largest separator two dense half-eliminations can afford. That essay records what five integers between three and six can support, which is less than a growth law.

Underneath the integer is a real number. A column count is a threshold laid across a list of singular values, and the threshold is a decision while the list is not. The list falls off a cliff, and how steeply it falls is a continuous quantity that keeps moving at the sizes where the count stalls.

This essay is about that quantity: what its first step actually measures, what it does not, and a control that was put in to flatten the cliff and made it nine hundred times steeper instead.

The first step of the cliff is one entry #

The largest singular value of that block is 1.2859. The largest entry of the block is 1.2690, and it sits in the corner — the coupling between the last unknown of the left half and the first unknown of the right, which are the two unknowns adjacent on the separator. The singular value is 98.7 per cent of that one entry.

That is not a coincidence of scale, and the cheapest way to see it is to remove the entry. Setting that single number of the block’s 132 to zero and recomputing takes the block’s two-norm from 1.2859 to 0.1952 — a factor of 6.6, from one entry out of a hundred and thirty-two, in a matrix whose every entry is nonzero. On the random-valued operator further down this page the same deletion takes it from 1.3075 to 1.867·10⁻³, a factor of 700.

So σ₁ is the near-field interaction at the point where the two halves meet, and it is very nearly nothing else. The first step of the cliff — σ₁ over σ₂, which is where nearly all of the saving is, because it is the step that decides whether one column will nearly do — is a ratio between that single contact and everything the two halves say to each other at a distance.

This is worth saying plainly because it is a different object from the one the compressibility argument is about. The reason the block is low rank is a statement about its far field: the entries are values of a smooth kernel, so distant rows are nearly multiples of one another. The reason its cliff has a large first step is a statement about its near field: two of the unknowns touch. The two are measured by the same spectrum and they are not the same claim.

The step gets shallower, and the peak is not what moves #

Across the three separators the block has room for a spectrum on, the first step runs 23.0, 19.1, 16.2. It falls monotonically while the separator doubles, which is the same doubling the integer count climbs across, in the opposite direction.

Both readings come from the same list and only one of them says which end moved. σ₁ is 1.2702, 1.2791 and 1.2859 at the three sizes — rising by less than half a per cent in total, and converging on the coupling between two adjacent unknowns of an infinite separator, which is a local quantity a longer separator cannot change much. σ₂ is 0.0552, 0.0670 and 0.0795 — rising by 44 per cent.

The cliff is getting shallower because the tail is growing, not because the peak is falling. A longer separator adds more pairs of points at a distance, so there is more far field to describe and the second singular value has more to be made of. That is the movement the integer count was reporting when it crept up by one column per size, and it is the movement the count stops reporting at thirty-one, where the sixth column is still enough and a seventh is not yet needed.

The rate is the better instrument for the same reason the stored share was a better instrument than the rank: it is not quantised. Three integers cannot distinguish a logarithm from a cube root. Three real numbers falling by 17 and 15 per cent across a doubling are still only three points, but they are three points that would have looked different had the underlying quantity done something else, and the integers would not.

The control was expected to be flat #

The way to find out whether a measured structure belongs to the object or to the measurement is to take the object away and measure again. The first essay of the hierarchy field does exactly that: it draws a kernel block whose singular values fall a factor of forty a column beside a block of independent draws on the same points, whose singular values do not fall at all.

The control available here is stronger, because it keeps more. It keeps the five-point pattern, so the graph is the same graph; it keeps the middle column as the separator, so the cut is the same cut; and it keeps the elimination, so the object is still a Schur complement. What it replaces is the values: every nonzero entry becomes a symmetric random draw, with a diagonal large enough to hold the matrix positive definite. There is no differential operator anywhere in it, so there is no Green’s function to be smooth.

The expectation was a flat spectrum. The measurement is the opposite.

A first step of 14,672 against 16.2, and a numerical rank of 2 of 11 against 6 of 11. The control is not a flat spectrum and it is not a weaker cliff; it is a far more compressible block than the one the field’s whole argument is about, arrived at by deleting the argument.

Where a cliff with no operator behind it comes from #

The block’s entries say it immediately. Along the row of the cross block nearest the contact, the Laplacian’s entries run 1.27, 0.118, 0.0601, 0.0343, 0.0212 and on down to 8.73·10⁻⁴ — a smooth decay through four decades. The random operator’s run 1.31, 1.84·10⁻³, 3.23·10⁻⁴, 2.77·10⁻⁵ and reach 3.09·10⁻¹² in the same eleven steps. Over the whole block, largest entry to smallest, the Laplacian spans a factor of 5.48·10⁴ and the random operator spans 4.26·10²³.

The mechanism is diagonal dominance, and the five-point stencil is the interesting case because it has none to spare. An interior row of it is a diagonal of 4 against four off-diagonal entries of −1: the row sum of the off-diagonals is exactly the diagonal, so the operator is diagonally dominant and not strictly so, at every interior point. The random operator’s diagonal is drawn near 8 against four off-diagonal entries drawn near zero, which makes its worst row ratio 1.277 and its mean 3.595.

Strict diagonal dominance is what makes an inverse decay exponentially with distance in the graph, and the Schur complement is a restriction of an inverse. The two-dimensional Laplacian has no such decay to inherit; its Green’s function falls off like a logarithm, which is slow, and its discrete cousin behaves the same way. So the random operator’s Schur complement is numerically almost banded, and a block taken between two halves of a separator is numerically almost a single entry.

That produces a low rank for a reason that has nothing to do with smoothness. A matrix whose entries fall below any given tolerance except in one corner has a small numerical rank at that tolerance because most of it is not there.

The test that tells a shape from a size #

Two mechanisms produce one reading, and there is a measurement that separates them. Divide every row of the block by its norm and then every column by its norm, and repeat until neither moves. That destroys the magnitudes and keeps the shape of every row and every column, so a rank that came from decay disappears and a rank that came from rows being nearly multiples of one another survives.

The Laplacian’s rank is entirely shape. Rescaled, its sixth singular value is still 9.3·10⁻⁷ of its first, the cliff is six decades long, and the count at eight digits is the same 6 it was. The control’s is entirely size. Rescaled, its second singular value goes from 6.8·10⁻⁵ to 0.343, its cliff is gone, and the block that needed two columns needs nine of a possible eleven — which is the flat spectrum the control was put in to produce, arriving one rescaling later than expected.

The anisotropic operator, which has the same diagonal balance as the Laplacian and no strict dominance, behaves like the Laplacian: 5 columns before and 5 after. Its compressibility is shape too.

What this says about the sentence under the cliff #

This collection explains the cliff by saying that the Schur complement of a discrete Laplacian is a discrete Green’s function, and that away from the diagonal a Green’s function is smooth. Every word of that is true, the rescaling above is direct evidence for it, and nothing here contradicts it.

What the control shows is narrower and worth stating exactly: the steepness of the cliff is not evidence of it. A steep cliff is consistent with a smooth kernel and equally consistent with an operator whose inverse decays exponentially, and those two are opposite situations for anyone deciding what to build. A reader who reads a first step of 14,672 as a smoother kernel than 16.2 has it backwards.

The instrument that does distinguish them is the rescaling, and the confirmation is what happens to the two ranks as the separator grows.

separator m 11 15 23 Laplacian, first step 23.0 19.1 16.2 Laplacian, columns 4 5 6 control, first step 34,065 14,964 14,672 control, columns 3 3 2

The two ranks move in opposite directions. The Laplacian’s climbs, which is what an off-diagonal rank does — the hierarchy field measures the same climb on a touching kernel block, and a rank that grows slowly with the size of the block is exactly the property a hierarchical format is built on. The control’s falls, from 3 to 3 to 2, because a longer separator puts more of its block below the tolerance rather than adding structure to it.

A rank that falls as the problem grows is not a bargain, it is a tolerance running out of things to see. It is also, at these three sizes, indistinguishable from a very good bargain if the only number read is the count.

The knob that moves the rate and stalls the count #

The site has a field about what happens to this operator when its two directions stop being equally weighted, and every method in it gets worse: a coarse grid stops representing one direction, a point smoother stops seeing it, and the anchor exists because of it. The fill goes the other way, which the count already establishes. As a rate it is much sharper.

At a separator of twenty-three, with ε running 1, 0.3, 0.1, 0.03 and 0.01, the first step runs 16.2, 24.1, 51.5, 165.4, 657.5 — monotone, and a factor of forty across the sweep. The column count over the same five operators runs 6, 5, 5, 4, 3: monotone as well, and it stalls twice in five steps. The rate has a reading at every setting and the count has three readings at five settings.

Rescaled, the anisotropic ranks are 6, 6, 5, 4 and 4 against the raw 6, 5, 5, 4, 3 — so the anisotropic cliff survives its magnitudes being taken away, and it is the same kind of cliff the Laplacian has. That is the test of the explanation this field already gives for it: a strongly anisotropic Green’s function is nearly a function of one coordinate, which is nearly separable, and separable is a statement about shape. The solver’s side of the same weak coupling reads it as an opportunity in one direction; here it is an opportunity in the other.

The count in that picture is doing what a count does. It sits at 5 for the first three operators, over a range across which the condition number more than doubles, and then it moves twice. Nothing about the underlying compressibility stalled; the threshold did.

The operator that refuses to be drawn #

There is a setting of that knob the picture will not take. An anisotropic five-point operator at ε = 1 is the Poisson stencil — the same matrix, entry for entry — so a figure asking for it draws a correct picture of an anisotropy that is not there. It renders perfectly, its numbers are all right, and its caption is false.

That case is refused rather than allowed, which is the only thing that can catch it: two placements with different captions, both individually correct, and every check green. It belongs with the reason a bound is not plotted outside its own range and is the same habit as the refusal at the head of this page — the assertion that a shuffled separator leaves a compressible block, fed the shuffled block, and required to fail. That control curve is in every picture here: 1, 0.84, 0.64, 0.63 at twenty-three unknowns, with no cliff at any size and no trend across the three.

Where this reading stops #

Four boundaries, and none of them is a hedge.

The rescaling is a diagnostic, not a method. No solver equilibrates a Schur complement before compressing it. A hierarchical format truncating the control’s block at eight digits keeps two columns and is right to: two columns really do describe it, and by exactly the amount the discarded singular value says. What the rescaling changes is not what to store today but what to expect at a separator ten times longer.

Three sizes are three sizes. The affordable range here is a factor of two in the separator, for the same reason the count’s range is: both half-eliminations are dense, and a dense factorisation of each half is cubic in a quantity that grows like k². The rate is a better-conditioned observable than the count over that range and it is not a longer one.

The control is one draw. Its cliff is a property of a diagonally dominant random operator rather than of any particular set of numbers, and the mechanism above predicts it without reference to the draw — but the figures are one seed, and nothing here rests on the exact value 14,672.

And a singular value below 10⁻¹⁶ of the first is noise. The rescaled spectra run down past that, the raw ones on the control run far past it, and every claim on this page is read at 10⁻⁸ or above for that reason.

What follows for anything that measures a fill #

Report the rate, not only the count. The stored share the host essay proposes is the right quantity for a memory budget and it is still built out of an integer: 2·rank/m moves only when the rank moves. The first step and the decay across the first four values move at every size, and they are read off the same decomposition the count is read off, for no extra work.

Do not read steepness as smoothness. The two operators on this page differ by a factor of nine hundred in their first step and by a factor of three in their column count, in opposite directions, and the steeper one has no differential operator behind it at all.

Check whether the rank grows with the block. That is the property a hierarchical representation is built on and it is the one the two mechanisms disagree about. A rank that falls as the separator lengthens is a tolerance effect and it will not survive being asked for more digits — which is the axis the essay on columns per decade holds fixed while this one moves the separator.

And the numbering still decides everything. Every figure here carries the renumbered curve, and it is flat in all of them: the Laplacian’s block, the control’s and the anisotropic one’s are each full or nearly full rank once the separator’s unknowns are shuffled. That is the permutation the hierarchy field measures arriving in a sparse factorisation, and here nobody chose it — nested dissection hands over a spatially coherent numbering as a side effect of cutting a small separator, which an ordering computed from the graph alone has no reason to do. The arrowhead matrix is the same lesson at the opposite extreme, where one row’s position decides whether there is any fill to compress.

The fill is dense, and the field’s first sentence about it is unchanged by anything here: 100 per cent of the entries of every Schur complement on this page are nonzero, including the control’s. What is not settled by that reading, and what a column count settles only coarsely, is how many of those entries are saying something new — and that is a real number with a slope, which is a different kind of measurement from an integer that stalls.