Numerical Linear Algebra
where the algebra stops being the arithmetic
Sparsity, and what elimination costs

The fill that is not independent

Eliminate both halves of a grid and what is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged. Its off-diagonal block is 11 by 12 and six columns describe it to eight digits. Renumber the separator and the same block needs all eleven.
36 min read 27 figures Where the algebra stops being the arithmeticMeasured, not assertedAssertions that reject

Worth reading first: The factor is not sparse · The order decides the memory · A block nobody can call sparse.

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 Schur complement left on a 15-unknown separator, shaded by the size of each entryA 15 × 15 grid, its middle column taken as a separator, and both halves eliminated exactly. What is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged: eliminating a variable couples everything it touched, and by the end everything is coupled to everything. The shading is what that field does not measure. The entries fall away smoothly from the diagonal, because the Schur complement is a discrete Green's function — the operator mapping data on the separator to response on the separator — and away from the diagonal that is an integral operator with a smooth kernel. The outlined block is the 7 × 8 between the separator's two halves: every entry nonzero, and 5 columns describe it to eight digits. The rank structure was not put there by the elimination. It was in the differential operator before anything was discretised.the separator's 15 unknowns, in the order they sit on the lineoutlined: the block between the two halvesdense, and not independententries nonzero1the block56columns it needs5numbers stored150entries in the square225every entry is nonzeroand six columns describe them
Fig. 1 The Schur complement on a fifteen-unknown separator, shaded by the size of each entry. Every entry is nonzero; the outlined block is 7 by 8 and five columns describe it.

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_rr⁻¹ A_rs .

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

grid separator nonzero block columns at 10⁻⁸ renumbered
7 7 100% 3 × 4 3 3
11 11 100% 5 × 6 4 5
15 15 100% 7 × 8 5 7
23 23 100% 11 × 12 6 11

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. 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 singular values of the fill between a separator's two halves, and of the same block renumberedThe block is 11 × 12, every entry of it nonzero, and its singular values fall by a factor of 16.2 at the first step and keep falling: 1, 0.062, 0.0039, 1.3·10⁻⁴, 2·10⁻⁶. That is the same cliff a block of a kernel matrix between two intervals has, and it is the same cliff for the same reason — the Schur complement of a discrete Laplacian is a discrete Green's function, so away from the diagonal it is an integral operator with a smooth kernel. The other curve is the same block after one symmetric permutation of the separator's unknowns: 1, 0.84, 0.64, 0.63, 0.57, which is a spectrum with no cliff in it at all. Both matrices have exactly the same entries.02468101210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹singular value, in orderσ ⁄ σ₁eight digitsrenumberedin the separator's orderthe same cliff, from the other endσ₂ ⁄ σ₁0.062σ₄ ⁄ σ₁1.3·10⁻⁴σ₆ ⁄ σ₁1.5·10⁻⁸renumbered σ₄ ⁄ σ₁0.63rank at 10⁻⁸6the same entriesin two orders
Fig. 2 The cliff, at the largest separator measured, with the same block renumbered beside it — where there is no cliff at all.
The singular values of one off-diagonal block, for four kernels on the same 96 pointsTwo intervals that do not touch — [0, 1] and [2, 3] — and the 96 × 96 block between them, for four kernels. 1/r falls a factor of 52 a column and is below 10⁻⁸ after 5; log r behaves the same way, for the reason the expansion makes obvious. An independent draw per entry gives 96 singular values above 10⁻⁸ out of 96, on the same size and the same density, which is what makes the other curves a measurement rather than a property of sorted numbers. The block has full algebraic rank in every case; what differs is where the numbers stop mattering, and that is a decision rather than a fact about the matrix.051015202530354010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, in orderσ ⁄ σ₁eight digitsan independent draw per entry1 ⁄ ra cliff, and a control1/r rank at 10⁻⁸5log r rank at 10⁻⁸5noise rank at 10⁻⁸96σ₂ ⁄ σ₁0.024σ₆ ⁄ σ₁2.8·10⁻⁹the block has full rankand five useful columns
Fig. 3 And the cliff this field’s first essay measures, on a block of 1/r between two intervals. The same shape, from the other direction.

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.

So the rank grows like the logarithm of the separator, which is what the hierarchy field’s third essay finds for a touching pair and not what it finds for an admissible one. 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.

Columns needed by the block between a separator's two halves, against the length of the separatorThe block is 3×4, 5×6, 7×8, 11×12 across the sweep, so its size more than triples. In the separator's own numbering — the unknowns in the order they sit on the line — it needs 3, 5, 6, 7 columns at 10⁻¹²: about one more per doubling, which is a logarithm. Renumber the same Schur complement by one symmetric permutation and the same block needs 3, 5, 7, 11 — all of them at eight digits and tighter, and a multiple of the geometric count at every tolerance drawn. Nothing about the matrix changed. What changed is that a cluster of a shuffled numbering is scattered along the whole separator, so every block mixes near interactions with far ones and there is no smooth kernel left to compress. The ordering that works here is not chosen: it is the one the separator's geometry already has, which is why nested dissection leaves a compressible fill and a fill-reducing ordering chosen on the graph alone need not.0481216202402468101214unknowns on the separatorcolumns above 10⁻¹²the same matrix, renumberedin the separator's own orderthe ordering the geometry hands overseparator 73separator 237renumbered, largest11the block, largest11share of the square stored0.61the fill is totaland it is not independent
Fig. 4 At twelve digits, where the geometric numbering needs seven columns and the renumbered one still needs all eleven.
Columns needed by the block between a separator's two halves, against the length of the separatorThe block is 3×4, 5×6, 7×8, 11×12 across the sweep, so its size more than triples. In the separator's own numbering — the unknowns in the order they sit on the line — it needs 2, 2, 2, 2 columns at 0.01: about one more per doubling, which is a logarithm. Renumber the same Schur complement by one symmetric permutation and the same block needs 3, 4, 6, 9 — all of them at eight digits and tighter, and a multiple of the geometric count at every tolerance drawn. Nothing about the matrix changed. What changed is that a cluster of a shuffled numbering is scattered along the whole separator, so every block mixes near interactions with far ones and there is no smooth kernel left to compress. The ordering that works here is not chosen: it is the one the separator's geometry already has, which is why nested dissection leaves a compressible fill and a fill-reducing ordering chosen on the graph alone need not.0481216202402468101214unknowns on the separatorcolumns above 0.01the same matrix, renumberedin the separator's own orderthe ordering the geometry hands overseparator 72separator 232renumbered, largest9the block, largest11share of the square stored0.17the fill is totaland it is not independent
Fig. 5 And at two, where the separator’s own numbering needs two columns of eleven and the renumbered one needs nine — the comparison at its sharpest, at the tolerance a reader would expect to blur it.

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.

Nonzeros in the Cholesky factor of the 12×12 grid Laplacian, by orderingA horizontal bar chart comparing the number of nonzero entries in the Cholesky factor under four elimination orderings, with reference marks for the matrix itself and for a dense factor.natural1739reverse Cuthill–McKee1354minimum degree1026nested dissection1413matrix: 408 entries · dense factor: 10440bandwidth 12 · 4.26× the matrixbandwidth 12 · 3.32× the matrixbandwidth 123 · 2.51× the matrixbandwidth 108 · 3.46× the matrixn = 144, five-point stencilevery ordering fills in; none avoids it
Fig. 6 The comparison as this field has always drawn it, from the essay that measured it: two orderings, and the entries each leaves in the factor.
What one symmetric permutation does to the storage, on a matrix it does not changeThe same 256 × 256 matrix, its rows and columns renumbered by one permutation and its columns by the same one. The condition number is 24.3948 either way, to eight digits; the Frobenius norm is 6139.964 either way, to twelve. Nothing a norm can see has moved. Clustered, the partition stores 27,008 numbers. Shuffled, the admissibility test finds no admissible pair anywhere — every cluster of a shuffled numbering spans the whole interval, so every q is infinite — and the format degenerates to dense storage exactly. The rule with no test to fail does worse than that: it compresses every off-diagonal block regardless, gets ranks up to 119 out of 128, and stores 118,208 numbers — 1.80 times the matrix it was compressing. A rank-119 factorisation of a 128-column block is a more expensive way to write down the block than the block.numbers stored, 256 × 256clustered, strong27,008clustered, weak24,064the dense matrix65,536shuffled, strong65,536shuffled, weak118,208the same matrix, twiceκ, clustered24κ, shuffled24‖A‖_F, clustered6140‖A‖_F, shuffled6140shuffled weak ⁄ dense1.8the compressibility is in the numberingand the numbering is not in the matrix
Fig. 7 And the property the entry count cannot see, from the hierarchy field: one permutation, and a representation that goes from 41 per cent of n² to 100.

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.

Fill growth under natural: the factor rises as n^1.49A log-log plot of nonzero count against matrix dimension. The matrix's own count is a straight line of slope one; the factor's is steeper; a dense factor is steeper still.10²10².³10²10³10⁴n (dimension)nonzerosdense factorfactor, n^1.49matrix, n^1.05grid Laplacians from 5×5 to 12×12fitted, not quoted
Fig. 8 The cost the real recursion achieves, from the essay that counts it, and the reason the top-level separator is where the memory goes.
Entries in U, against the bound the symbolic phase can compute, on the 5×5 gridA row of horizontal bars. The topmost is longest and is labelled as the bound; every measured bar below it is shorter.the bound211no pivoting127τ = 0.00198τ = 0.003100τ = 0.01106τ = 0.03111τ = 0.1116τ = 0.3117τ = 1138entries in Ua bound, and its slackthe bound, from the graph alone211the worst that occurs138loose by1.5no arithmetic was done to compute the bound — only the pattern of AᵀA and its elimination graphGeorge and Ng: U fits inside chol(AᵀA), whatever the swapsprovable, cheap, and loose
Fig. 9 And the phase of a sparse solver that decides the structure in advance, which is the direct relative of this phase’s admissibility test.

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.

‖A − LLᵀ‖ ⁄ ‖A‖ for a Cholesky computed in the format, against how many truncations it performedThe recursion is the textbook one and every step stays in the format: the off-diagonal factor is exact, because a triangular solve against one factor of a rank-k block leaves a rank-k block, and the Schur complement is a rank-k addition to a hierarchical matrix, which is the only approximate step there is. So the number of truncations is a count — one per admissible block in the subtree being updated, at every level — and it runs from 0 at a leaf of 128 to 98 at a leaf of 8. The residual goes from 2.119·10⁻¹⁰ to 1.138·10⁻⁹, and all of that movement is the representation, whose own error is the upper curve and moves by the same factor: the ratio between them is 1.00, 0.93, 0.92, 0.91, 0.81, never above one. A hundred approximate operations contributed nothing measurable to the answer.02040608010010⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸truncations performed by the factorisationrelative errorthe representation's own error‖A − LLᵀ‖ ⁄ ‖A‖no decomposition without its residualresidual, 0 truncations2.1·10⁻¹⁰residual, 98 truncations1.1·10⁻⁹representation, deepest1.4·10⁻⁹residual ⁄ representation0.81levels, deepest5a hundred approximate stepsand an exact-looking factorisation
Fig. 10 The second ingredient, from the hierarchy field: a factorisation performed entirely inside the format, whose residual does not notice the arithmetic it was done with.
Applications of an operator that is never assembled, against the entries of the matrix it stands forThe blocks at one level of the tree have disjoint column supports, so one batch of random vectors samples all of them at once: two batches a level for the ranges, two more for the projections, and one batch of leaf products for every diagonal block in the matrix together. That is leaf + 2(2k + p)·levels products, and the counter inside the operator says 112, 160, 208, 256 at n = 64, 128, 256, 512 — 48 more per doubling, which is a logarithm. The other line is n², the entries the compression route reads. At n = 512 that is 256 products against 262,144 entries, and the representation it produces is within 7.3× of the one that read them all.567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48‖A − A_H‖ ⁄ ‖A‖4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read
Fig. 11 And the third, from the randomised field: a representation built from a few hundred applications of an operator that is never assembled.

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:

ε κ of the complement columns at 10⁻⁸ nonzero
1 13.1 5 100%
0.3 20.6 5 100%
0.1 32.0 4 100%
0.03 51.5 3 100%
0.01 72.5 3 100%

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 the anisotropy does to the compressibility of the fill, on the operator this site has a field aboutThe five-point operator's two directions stop being equally weighted, ε running from 1 down to 0.01, and the condition number of what is left on the separator rises from 13.1 to 72.5. Every method in the iterative field gets worse across this sweep: a point smoother stops seeing one direction, a coarse grid stops representing it, and the whole anisotropy anchor exists because of it. The fill goes the other way. Its rank falls 5, 5, 4, 3, 3 — a strongly anisotropic Green's function is *closer* to separable than an isotropic one, because coupling along the weak direction has almost vanished and what is left is nearly a function of one coordinate. The fill stays 100 per cent nonzero throughout, so nothing about the amount of fill is moving; only the amount of information in it.-2-1002468log₁₀ of the anisotropy εcolumns above 10⁻⁸columns the fill needsharder, and more compressiblerank at ε = 15rank at ε = 0.013κ at ε = 113κ at ε = 0.0173entries nonzero1the operator got worseand the fill got cheaper
Fig. 12 The sweep, with the density on the badge so that the falling rank cannot be read as the fill going away.
The same aggregates, with and without the prolongator smoothing (ε = 0.01)Relative residual against V-cycle on a logarithmic vertical axis. Both hierarchies are built from the identical aggregation of the same matrix. Without the smoothing sweep the convergence factor is 0.7051; with it the factor is 0.1923, reached in 13 cycles. The smoothed hierarchy stores 2.71 times the fine matrix against 1.51.036912151810⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹V-cyclerelative residualpiecewise constantsmoothedone sweep on the columns of Pfactor, unsmoothed0.71factor, smoothed0.19operator complexity, smoothed2.7the same aggregates in bothand one sweep between them
Fig. 13 And the same operator in the field where it is the difficulty, from the essay that measures what a smoother loses when the two directions separate.

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 Schur complement left on a 11-unknown separator, shaded by the size of each entryA 11 × 11 grid, its middle column taken as a separator, and both halves eliminated exactly. What is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged: eliminating a variable couples everything it touched, and by the end everything is coupled to everything. The shading is what that field does not measure. The entries fall away smoothly from the diagonal, because the Schur complement is a discrete Green's function — the operator mapping data on the separator to response on the separator — and away from the diagonal that is an integral operator with a smooth kernel. The outlined block is the 5 × 6 between the separator's two halves: every entry nonzero, and 4 columns describe it to eight digits. The rank structure was not put there by the elimination. It was in the differential operator before anything was discretised.the separator's 11 unknowns, in the order they sit on the lineoutlined: the block between the two halvesdense, and not independententries nonzero1the block30columns it needs4numbers stored88entries in the square121every entry is nonzeroand six columns describe them
Fig. 14 At a small separator, where the ridge is coarse and the falling away is still visible.
The two 6×6 matrices of a Sylvester equation, and the 36×36 matrix it meansA and B are 6×6 with 11 nonzeros each. The coefficient matrix of the map X ↦ AX + XB is 36×36 with 96 nonzeros, drawn at the same scale so the ratio is visible rather than quoted. Bartels and Stewart's algorithm never forms it: two Schur reductions and a back-substitution give the same X to 1.7·10⁻¹⁶, and that X satisfies AX + XB = C to 2·10⁻¹⁶.A6×6B6×6I ⊗ A + Bᵀ ⊗ I36×36one equation, two objectsentries in A and B72entries in the coefficient matrix1296two routes, relative gap1.7·10⁻¹⁶‖AX + XB − C‖/‖C‖2·10⁻¹⁶the small squares are the problemand the large one is the notation
Fig. 15 A pattern that is all a spy plot can say, from the structure field, where the interesting property of the matrix is not in its zeros at all.

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.

The Schur complement left on a 23-unknown separator, shaded by the size of each entryA 23 × 23 grid, its middle column taken as a separator, and both halves eliminated exactly. What is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged: eliminating a variable couples everything it touched, and by the end everything is coupled to everything. The shading is what that field does not measure. The entries fall away smoothly from the diagonal, because the Schur complement is a discrete Green's function — the operator mapping data on the separator to response on the separator — and away from the diagonal that is an integral operator with a smooth kernel. The outlined block is the 11 × 12 between the separator's two halves: every entry nonzero, and 6 columns describe it to eight digits. The rank structure was not put there by the elimination. It was in the differential operator before anything was discretised.the separator's 23 unknowns, in the order they sit on the lineoutlined: the block between the two halvesdense, and not independententries nonzero1the block132columns it needs6numbers stored276entries in the square529every entry is nonzeroand six columns describe them
Fig. 16 At the largest separator measured, where the ridge along the diagonal is clearer and the outlined block is 11 by 12.
The 12×12 grid Laplacian and its Cholesky factor, ordered by naturalTwo square sparsity plots side by side. The left shows the nonzeros of the matrix; the right shows the nonzeros of its Cholesky factor, with the entries created by elimination marked in a second colour.the matrix, lower triangle408 entriesits Cholesky factor1739 entries · 1331 created→‖A − LLᵀ‖/‖A‖1.4·10⁻¹⁶fill, symbolic1331fill, numeric1331n = 144 · density 3.2% · bandwidth 12same matrix, renumberedthe answer is identical to rounding
Fig. 17 The pattern this field draws for the same operator, from the essay that counts it: which entries the elimination fills in, before anybody asks what is in them.
Columns needed by the block between a separator's two halves, against the length of the separatorThe block is 3×4, 5×6, 7×8, 11×12 across the sweep, so its size more than triples. In the separator's own numbering — the unknowns in the order they sit on the line — it needs 3, 4, 4, 5 columns at 10⁻⁶: about one more per doubling, which is a logarithm. Renumber the same Schur complement by one symmetric permutation and the same block needs 3, 5, 7, 10 — all of them at eight digits and tighter, and a multiple of the geometric count at every tolerance drawn. Nothing about the matrix changed. What changed is that a cluster of a shuffled numbering is scattered along the whole separator, so every block mixes near interactions with far ones and there is no smooth kernel left to compress. The ordering that works here is not chosen: it is the one the separator's geometry already has, which is why nested dissection leaves a compressible fill and a fill-reducing ordering chosen on the graph alone need not.0481216202402468101214unknowns on the separatorcolumns above 10⁻⁶the same matrix, renumberedin the separator's own orderthe ordering the geometry hands overseparator 73separator 235renumbered, largest10the block, largest11share of the square stored0.43the fill is totaland it is not independent
Fig. 18 And the growth at six digits, where the two curves separate at the second point and never meet again.

Both fields, on one object

Columns needed by the block between a separator's two halves, against the length of the separatorThe block is 3×4, 5×6, 7×8, 11×12 across the sweep, so its size more than triples. In the separator's own numbering — the unknowns in the order they sit on the line — it needs 3, 5, 5, 6 columns at 10⁻¹⁰: about one more per doubling, which is a logarithm. Renumber the same Schur complement by one symmetric permutation and the same block needs 3, 5, 7, 11 — all of them at eight digits and tighter, and a multiple of the geometric count at every tolerance drawn. Nothing about the matrix changed. What changed is that a cluster of a shuffled numbering is scattered along the whole separator, so every block mixes near interactions with far ones and there is no smooth kernel left to compress. The ordering that works here is not chosen: it is the one the separator's geometry already has, which is why nested dissection leaves a compressible fill and a fill-reducing ordering chosen on the graph alone need not.0481216202402468101214unknowns on the separatorcolumns above 10⁻¹⁰the same matrix, renumberedin the separator's own orderthe ordering the geometry hands overseparator 73separator 236renumbered, largest11the block, largest11share of the square stored0.52the fill is totaland it is not independent
Fig. 19 The growth at ten digits, where the geometric numbering needs six columns and the renumbered one still needs all eleven.
The singular values of the fill between a separator's two halves, and of the same block renumberedThe block is 7 × 8, every entry of it nonzero, and its singular values fall by a factor of 19.1 at the first step and keep falling: 1, 0.052, 0.0019, 2.2·10⁻⁵, 7.9·10⁻⁸. That is the same cliff a block of a kernel matrix between two intervals has, and it is the same cliff for the same reason — the Schur complement of a discrete Laplacian is a discrete Green's function, so away from the diagonal it is an integral operator with a smooth kernel. The other curve is the same block after one symmetric permutation of the separator's unknowns: 1, 0.65, 0.62, 0.53, 0.49, which is a spectrum with no cliff in it at all. Both matrices have exactly the same entries.0246810⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹singular value, in orderσ ⁄ σ₁eight digitsrenumberedin the separator's orderthe same cliff, from the other endσ₂ ⁄ σ₁0.052σ₄ ⁄ σ₁2.2·10⁻⁵σ₆ ⁄ σ₁6.3·10⁻¹¹renumbered σ₄ ⁄ σ₁0.53rank at 10⁻⁸5the same entriesin two orders
Fig. 20 The cliff at a shorter separator, where there is less of it to see and the shape is the same.
What the anisotropy does to the compressibility of the fill, on the operator this site has a field aboutThe five-point operator's two directions stop being equally weighted, ε running from 1 down to 0.01, and the condition number of what is left on the separator rises from 9.7 to 46.0. Every method in the iterative field gets worse across this sweep: a point smoother stops seeing one direction, a coarse grid stops representing it, and the whole anisotropy anchor exists because of it. The fill goes the other way. Its rank falls 4, 4, 4, 3, 3 — a strongly anisotropic Green's function is *closer* to separable than an isotropic one, because coupling along the weak direction has almost vanished and what is left is nearly a function of one coordinate. The fill stays 100 per cent nonzero throughout, so nothing about the amount of fill is moving; only the amount of information in it.-2-1001234567log₁₀ of the anisotropy εcolumns above 10⁻⁸columns the fill needsharder, and more compressiblerank at ε = 14rank at ε = 0.013κ at ε = 19.7κ at ε = 0.0146entries nonzero1the operator got worseand the fill got cheaper
Fig. 21 The anisotropy sweep on a smaller grid, where the direction of the effect is the same and the ranks are one apart.
The Schur complement left on a 7-unknown separator, shaded by the size of each entryA 7 × 7 grid, its middle column taken as a separator, and both halves eliminated exactly. What is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged: eliminating a variable couples everything it touched, and by the end everything is coupled to everything. The shading is what that field does not measure. The entries fall away smoothly from the diagonal, because the Schur complement is a discrete Green's function — the operator mapping data on the separator to response on the separator — and away from the diagonal that is an integral operator with a smooth kernel. The outlined block is the 3 × 4 between the separator's two halves: every entry nonzero, and 3 columns describe it to eight digits. The rank structure was not put there by the elimination. It was in the differential operator before anything was discretised.the separator's 7 unknowns, in the order they sit on the lineoutlined: the block between the two halvesdense, and not independententries nonzero1the block12columns it needs3numbers stored42entries in the square49every entry is nonzeroand six columns describe them
Fig. 22 The Schur complement at the smallest separator, where the ridge is four cells wide and already falling away from the diagonal.
The rank of an admissible block and of a touching one, against how finely they are sampledBoth blocks are of the kernel 1/r; both are 32, 64, 128, 256 points a side; both are truncated at 10⁻⁸. The admissible pair — [0, 1] against [2, 3] — needs 5, 5, 5, 5 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 9, 11, 12, 13, climbing by about one per doubling, which is a logarithm. Neither of them grows like the block, and only one of them stops. That difference is what the admissibility test in a partition is buying, and it is why the touching pair is kept dense rather than compressed at all.45678903691215log₂ of the points a sidecolumns above 10⁻⁸two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 325admissible, n = 2565touching, n = 329touching, n = 25613stored ⁄ dense at largest0.039the rank belongs to the geometryand not to the sampling
Fig. 23 The hierarchy field’s version of this growth, where the block being measured is a kernel evaluated at two sets of points rather than what an elimination left.
The singular values of one off-diagonal block, for four kernels on the same 128 pointsTwo intervals that do not touch — [0, 1] and [2, 3] — and the 128 × 128 block between them, for four kernels. 1/r falls a factor of 52 a column and is below 10⁻⁸ after 5; log r behaves the same way, for the reason the expansion makes obvious. An independent draw per entry gives 128 singular values above 10⁻⁸ out of 128, on the same size and the same density, which is what makes the other curves a measurement rather than a property of sorted numbers. The block has full algebraic rank in every case; what differs is where the numbers stop mattering, and that is a decision rather than a fact about the matrix.051015202530354010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, in orderσ ⁄ σ₁eight digitsan independent draw per entry1 ⁄ ra cliff, and a control1/r rank at 10⁻⁸5log r rank at 10⁻⁸5noise rank at 10⁻⁸128σ₂ ⁄ σ₁0.024σ₆ ⁄ σ₁2.8·10⁻⁹the block has full rankand five useful columns
Fig. 24 And the cliff it measures, which is the same cliff for the same reason.
A 256 × 256 kernel matrix partitioned by the strong rule, with each compressed block's rank112 blocks: 46 kept dense and 66 stored as two thin factors, whose ranks run from 4 to 5. The rule decides one thing — whether a pair of index clusters may be compressed — and it decides it from four numbers about where those clusters sit, before any entry of the matrix is read. The strong rule refuses any pair whose clusters touch, and subdivides instead, so the diagonal is fringed with small dense blocks and no rank on the picture exceeds 5. The whole thing stores 27,008 numbers against 65,536 entries, and reproduces the matrix to 3.41·10⁻¹⁰.545545545455554545545545545454555555454545545545545455554545545545rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe strong partitionblocks112kept dense46largest rank5numbers stored2.7·10⁴‖A − A_H‖ ⁄ ‖A‖3.4·10⁻¹⁰the picture is decidedbefore a number is read
Fig. 25 What a representation of this Schur complement would look like: a partition whose pieces away from the middle of the separator are genuinely admissible.
‖A − LLᵀ‖ ⁄ ‖A‖ for a Cholesky computed in the format, against how many truncations it performedThe recursion is the textbook one and every step stays in the format: the off-diagonal factor is exact, because a triangular solve against one factor of a rank-k block leaves a rank-k block, and the Schur complement is a rank-k addition to a hierarchical matrix, which is the only approximate step there is. So the number of truncations is a count — one per admissible block in the subtree being updated, at every level — and it runs from 0 at a leaf of 128 to 98 at a leaf of 8. The residual goes from 2.119·10⁻¹⁰ to 1.138·10⁻⁹, and all of that movement is the representation, whose own error is the upper curve and moves by the same factor: the ratio between them is 1.00, 0.93, 0.92, 0.91, 0.81, never above one. A hundred approximate operations contributed nothing measurable to the answer.02040608010010⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸truncations performed by the factorisationrelative errorthe representation's own error‖A − LLᵀ‖ ⁄ ‖A‖no decomposition without its residualresidual, 0 truncations2.1·10⁻¹⁰residual, 98 truncations1.1·10⁻⁹representation, deepest1.4·10⁻⁹residual ⁄ representation0.81levels, deepest5a hundred approximate stepsand an exact-looking factorisation
Fig. 26 The second ingredient a rank-structured sparse solver needs, from the hierarchy field.
Applications of an operator that is never assembled, against the entries of the matrix it stands forThe blocks at one level of the tree have disjoint column supports, so one batch of random vectors samples all of them at once: two batches a level for the ranges, two more for the projections, and one batch of leaf products for every diagonal block in the matrix together. That is leaf + 2(2k + p)·levels products, and the counter inside the operator says 112, 160, 208, 256 at n = 64, 128, 256, 512 — 48 more per doubling, which is a logarithm. The other line is n², the entries the compression route reads. At n = 512 that is 256 products against 262,144 entries, and the representation it produces is within 7.3× of the one that read them all.567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512256entries at n = 5122.6·10⁵per doubling48‖A − A_H‖ ⁄ ‖A‖4·10⁻⁷excess over the compression7.3no entry of the matrixwas ever read
Fig. 27 And the third, from the randomised field, which matters because a Schur complement is exactly the kind of object that can be applied and would rather not be formed.

Where this goes next

the matrix, lower triangle408 entriesits Cholesky factor1739 entries · 1331 created→‖A − LLᵀ‖/‖A‖1.4·10⁻¹⁶fill, symbolic1331fill, numeric1331n = 144 · density 3.2% · bandwidth 12same matrix, renumberedthe answer is identical to rounding The factor is not sparse A sparse matrix has a factor that is not sparse, and the gap between them is the entire reason iterative methods exist. The entries elimination creates can be counted before any arithmetic runs, from the graph alone. natural1739reverse Cuthill–McKee1354minimum degree1026nested dissection1413matrix: 408 entries · dense factor: 10440bandwidth 12 · 4.26× the matrixbandwidth 12 · 3.32× the matrixbandwidth 123 · 2.51× the matrixbandwidth 108 · 3.46× the matrixn = 144, five-point stencilevery ordering fills in; none avoids it The order decides the memory Four elimination orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries. All four factorisations are exact, all four return the same answer, and the one with the better asymptotics is not the one that wins. 051015202530354010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, in orderσ ⁄ σ₁eight digitsan independent draw per entry1 ⁄ ra cliff, and a control1/r rank at 10⁻⁸5log r rank at 10⁻⁸5noise rank at 10⁻⁸96σ₂ ⁄ σ₁0.024σ₆ ⁄ σ₁2.8·10⁻⁹the block has full rankand five useful columns A block nobody can call sparse A 96 × 96 block of a kernel matrix has ninety-six nonzero singular values and five that matter. It has no zero entries, it is not described by fewer numbers than it contains, and neither of the two ways this collection already knows to make a large matrix affordable applies to it.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Elimination orderFill-inFill-reducing orderingGreens functionHierarchical matrixKernel matrixNested dissectionNumerical rankOff diagonal rankSeparator