The fill that is not independent

The sparsity field opens on a sentence and stops one question short of the next one.

The sentence is that the factors of a sparse matrix are not sparse: eliminating a variable couples everything it touched to everything else it touched, and every one of those couplings is an entry that was zero and is not. The factor is not sparse counts them; the order decides the memory shows that the elimination order decides how many; and nested dissection is the order that does best on a grid — and even it leaves a separator whose Schur complement is completely full.

That is where the field stops. The question it stops before is whether all those entries are independent.

The experiment #

A k × k grid with the five-point operator. Take the middle column as a separator, and eliminate the left half and the right half exactly — a dense factorisation of each, which is affordable at these sizes and is the point, since what is being measured is the object left behind rather than the cost of reaching it.

What is left on the separator is

S = A_ss − A_sl A_ll⁻¹ A_ls − A_sr Aᵣᵣ⁻¹ A_rs .

Count its nonzero entries, bisect it, and take the numerical rank of the block between its two halves:

Three things in one table. The complement is completely dense, at every size, which is the sparsity field’s result unchanged. Its cross block is not full rank, and the gap widens: 6 of 11 at the largest separator. And the last column is the same Schur complement after one symmetric permutation of the separator’s unknowns, where the same block needs all of them.

Why the fill is not independent #

The Schur complement is a discrete Green’s function.

Eliminating the interior of a domain is exactly the operation that leaves, on its boundary, the operator mapping boundary data to boundary response — the object a hierarchical format is built to hold. In the continuous problem that operator is an integral operator whose kernel is the Green’s function of the differential operator restricted to the boundary — and away from the diagonal, a Green’s function is smooth.

So the block between two halves of the separator is a kernel matrix between two well-separated sets of points, which is the object the first essay of the hierarchy field measures. Its singular values fall off a cliff:

1, 6.18·10⁻², 3.90·10⁻³, 1.25·10⁻⁴, 1.97·10⁻⁶, 1.46·10⁻⁸, 4.83·10⁻¹¹

which is the same shape as the block between [0, 1] and [2, 3] for the kernel 1/r, arrived at from completely the other end.

The rank structure was not put there by the elimination. It was in the differential operator before anything was discretised, and the elimination made it visible by producing the matrix whose entries are values of it.

The growth, and what it is #

The rank column climbs 3, 4, 5, 6 while the block climbs 3, 5, 7, 11 — that is 1.78 columns per doubling of the separator, against 0.19 columns per unknown. A full block would give 0.5 per unknown by construction.

That looks like a logarithm, which is what the hierarchy field’s third essay finds for a touching pair and not what it finds for an admissible one — and the section after next is about how much of that reading four points can actually support. That is the right answer and it has a reason: the two halves of a separator touch. They share an endpoint at the middle of the line, the block between them contains the near-field interaction there, and the expansion the whole argument rests on does not converge across it.

A hierarchical representation of the Schur complement would therefore subdivide, exactly as the hierarchy field’s partition does, and the pieces away from the middle would be genuinely admissible. What this table measures is the crudest possible version — one bisection, one block — and it is already enough to make the point, which is that the fill is compressible and by how much is a question with a familiar shape.

The share of the block that has to be stored is 2·rank/m, and it falls: 0.86, 0.73, 0.67, 0.52 across the four sizes. Not dramatic at a separator of 23, and falling at every step, which is the form of the claim worth making.

What five integer ranks can support, which is less than a law #

Four points in an arithmetic progression against a doubling axis is exactly what a logarithm looks like. It is also what a square root looks like, and a cube root, when the observable is an integer between three and six.

The largest separator the two dense half-factorisations can afford is 31, one step past the table. The rank there is 6 — the same as at 23.

separator m 7 11 15 23 31 rank at 10⁻⁸ 3 4 5 6 6

The progression stops. The 1.78 columns per doubling fitted on the first four predicts 6.8 at m = 31, so the one point beyond the data the rate was fitted on is the one it misses, and it misses it in the direction that matters — the growth is slower than the fit, not faster.

And the tolerance is a second axis the table holds fixed, which changes what the ranks mean.

Only the good ordering’s ranks move. Tightening the tolerance from 10⁻⁴ to 10⁻¹² takes the geometric ordering’s rank at the largest separator from 4 to 5, 6, 6 and 7, while the shuffled ordering goes 10, 10, 11, 11, 11 and the block ordering sits at 11 at every one of the five tolerances. The two bad orderings are already at the block’s full rank and have nothing left to give.

The first of the four blocks never moves: 3 at every tolerance on the slider. The last gains a rank roughly every three decades. So the spread between the cheapest block and the dearest widens as the tolerance tightens — 2 at 10⁻⁶, 3 at 10⁻¹⁰ — and a storage estimate made at one tolerance does not rescale to another.

So the ordering’s advantage is a function of how much accuracy is being asked for, and it shrinks as more is asked. At the largest separator the ratio of shuffled rank to geometric rank runs 2.5, 2.0, 1.8, 1.8 and 1.6 across those five tolerances. That is the honest form of the saving: it is largest where the least is demanded, and a benchmark run at 10⁻⁴ overstates by more than half what the same ordering is worth at 10⁻¹². It also bounds the whole argument — at any tolerance a double can express, the good ordering’s rank stays under two-thirds of the bad one’s, so the saving never disappears and never becomes the order of magnitude a reader might extrapolate towards.

None of that says the rank is not logarithmic. It says this measurement cannot tell, because the affordable range spans one octave of an integer and every candidate law is inside the quantisation. Fitting rank against m gives an exponent of 0.47 and fitting it against log m gives 1.22, and neither of those two numbers means anything: they are fits to five integers.

What does survive is the quantity that is not an integer. The share of the block that has to be stored, 2·rank/m, runs 0.86, 0.73, 0.67, 0.52, 0.39 — falling at every step, monotonically, including the step the rank did not take. That is the claim the field actually needs, it needs no growth law to state, and it is what the essay’s own “not dramatic at a separator of 23, and falling at every step” was reaching for.

And subdividing shows the structure without yet showing a saving #

The section above says a hierarchical representation would subdivide, and that the pieces away from the middle would be genuinely admissible. That is testable at the one size where it fits.

Splitting the m = 31 separator into quarters, the three touching pairs have ranks 5, 6 and 6; the three far pairs have 4, 5 and 4. The separation is there and it is in the right direction, which is the hierarchy field’s whole partition appearing inside a sparse factorisation with nobody having put it there.

And it buys nothing. The quarters are seven unknowns wide, so a rank of four stores 8 numbers of a possible 49 in the best case and 10 in the worst — before any of the bookkeeping a hierarchical format needs. The structure is visible at the sizes this measurement can reach and the benefit is not.

That is the honest boundary of this essay, and it is a boundary of the experiment rather than of the claim. Real separators are not 31 unknowns; a nested dissection of a 1,000-square has separators of a thousand, where a rank that has crept up to fifteen or twenty stores three per cent of the block. The argument that the fill is compressible does not need the subdivision to pay at m = 31 — it needs the share to be falling, which it is at every size measured, and it needs the mechanism to be a Green’s function, which is an argument about the differential operator and not about any grid.

The ordering, which is handed over rather than chosen #

The last column of the first table is the phase’s own finding arriving in this field, and the way it arrives is the interesting part.

The hierarchy field’s seventh essay takes a kernel matrix and permutes it, and the compressibility vanishes: the same matrix, the same spectrum, the same norm, and a representation that stores every entry. The numbering there is chosen by a spatial sort, deliberately, as a preprocessing step.

Here it is not chosen. The separator is a line of grid points, they arrive in the order they sit on the line, and that order is already the spatially coherent one. Nested dissection produces a compressible fill as a side effect of producing a small one, and nobody had to decide anything.

That is a genuinely lucky property and it is worth saying which part of it is luck. The luck is that a separator is a geometric object — a cut through a mesh — so its unknowns come with positions. A fill-reducing ordering chosen from the graph alone, by minimum degree say, produces separators that are sets of vertices with no particular spatial coherence, and there is no reason for the fill it leaves to be compressible in any ordering the algorithm knows about.

So the two orderings this field already compares — minimum degree against nested dissection — differ in a second way nobody was counting. One of them leaves less fill; the other leaves less fill and leaves it in a form that can be compressed further, and the second property is invisible in every count of entries.

Where the elimination cost went #

There is an accounting point in this experiment that is easy to lose and worth keeping, because it says why the measurement is about the object and not about the method.

The two half-eliminations above are dense. A 23 × 23 grid has 253 unknowns in each half, and factorising each half densely costs about 253³/3 ≈ 5.4·10⁶ multiplications — which is a preposterous way to eliminate a sparse matrix and is deliberately not what a sparse solver does. A real nested dissection recurses: each half is itself split by its own separator, and the cost comes out at O(n^1.5) rather than O(n^3).

None of that changes S. The Schur complement on the separator is the same matrix however the interior was eliminated, because it is defined by the algebra rather than by the algorithm — A_ss − A_sl A_ll⁻¹ A_ls is one expression, and any exact elimination of the interior produces it.

So the expensive route above is a way of getting a correct S at these sizes with the least code, and the measurements on it transfer unchanged to a solver that got there properly. What does not transfer is any statement about cost, which is why there is none in this essay.

The one thing worth noticing about the real recursion is that it makes the result more useful rather than less. In a proper nested dissection there is not one separator but a tree of them, each level’s separator carrying a Schur complement of its own, and the largest of them — the top-level separator of an n-unknown grid — has √n unknowns and a dense complement of n entries. That is the object that dominates the memory of a sparse direct solver in two dimensions, and it is the object this essay says is compressible.

What this is the beginning of #

The measurement above is the observation that a whole class of sparse direct solvers is built on, and it is worth naming what they do with it even though none of it is in this essay.

If the Schur complement on a separator is rank-structured, it can be stored rank-structured — and then the elimination that produces the next separator up the tree can be performed in the format, using the formatted arithmetic this phase measures. What comes out is a sparse direct solver whose complexity is O(n) or O(n log n) rather than the O(n^1.5) in two dimensions and O(n²) in three that nested dissection alone achieves.

That is a large claim and this essay establishes only its first ingredient. Two more are needed and both are elsewhere in this phase: that a formatted arithmetic does not lose accuracy across a chain of operations, which is the essay on ninety-eight truncations costing nothing; and that the representation can be built from products rather than entries, which matters because a Schur complement is exactly the kind of object that can be applied and would rather not be formed.

The anisotropy, which goes the other way #

The site has a whole field about what happens to this operator when its two directions stop being equally weighted, and every method in it gets worse. A point smoother stops seeing one direction, a coarse grid stops representing it, and the anchor exists because of it.

The fill goes the other way:

The operator gets harder by a factor of five in the condition number, the fill stays total, and the number of columns needed falls.

The reason is the same one that makes the whole field work. A strongly anisotropic operator couples weakly along one axis, so its Green’s function is nearly a function of one coordinate — which is to say nearly separable, which is exactly the property a low-rank block needs. The thing that makes an iteration struggle is the thing that makes the fill cheap.

That is a genuinely unexpected direction and it is worth one sentence of caution: it is measured on one grid at one bisection, and κ of a Schur complement is not κ of the operator. What it is not is an artefact of the fill becoming sparse, which is why the last column is on the table.

What a picture of the fill shows that a count does not #

This field draws fill as a pattern: which entries are there and which are not. That is the right picture for the question the field asks, and it is the wrong picture for this one.

A spy plot of the Schur complement above is a solid square. It carries exactly one bit of information — everything is nonzero — and it is the same solid square at every grid size and for every operator on the table, including the anisotropic ones and the random control.

Shading by magnitude carries the rest. What appears is a ridge along the diagonal falling away smoothly in both directions, and that is the structure the rank measurement is about: a matrix whose entries are a smooth function of the distance between two indices. The same shading on the random control shows no ridge and no falling away, and its cross block is full rank.

So the two pictures answer two questions and only one of them has been asked in this field before. Which entries are there is a question about the graph, it is answered by the symbolic phase, and it is what decides how much memory to allocate. What is in them is a question about the operator, nothing in the sparsity field asks it, and it decides how much of that memory is actually needed.

The general form is one this collection has met in the spectra field. A sparsity pattern and a spectrum are both summaries of a matrix; a matrix has many properties neither of them records; and a method built on one of them is blind to everything the other would have said.

The refusal #

The claim under test is the one this field’s own results would leave standing: that a dense Schur complement has to be stored as a dense matrix.

The refusal is fed the sparsity reading rather than the rank one, which is the way round that matters. The assertion that the complement is under half nonzero is handed 100 per cent, and it fails — so nothing in this essay may be read as softening the field’s original result. The fill is total. Every entry is there.

What is added is that 2·6·23 = 276 numbers describe the 11 × 12 block that 132 of those entries make up, and that the same block in a shuffled numbering needs all eleven columns. Dense and independent are two different words, this field measured the first, and only the second decides what has to be stored.