Numerical Linear Algebra
where the algebra stops being the arithmetic
Neither sparse nor dense

The size the rank does not notice

Sample a kernel block at 32, 64, 128 and 256 points a side and it needs five columns, five, five and five. Sample the touching block next to it at the same four sizes and it needs nine, eleven, twelve and thirteen. Same kernel, same accuracy, one number and a logarithm.
36 min read 28 figures Measured, not assertedWhere the algebra stops being the arithmeticAssertions that reject

Worth reading first: A block nobody can call sparse · The stencil that is not symmetric · Rank is a decision.

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 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. 1 The rank of an admissible block and of a touching one, against how finely each is sampled. One of them is a horizontal line and the other is not.

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:

points a side block columns at 10⁻⁸
32 32 × 32 5
64 64 × 64 5
128 128 × 128 5
256 256 × 256 5

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⁻⁸:

points a side admissible touching
32 5 9
64 5 11
128 5 12
256 5 13

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.

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 9, 9, 9, 9 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 14, 16, 19, 21, 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.45678904812162024log₂ of the points a sidecolumns above 10⁻¹⁴two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 329admissible, n = 2569touching, n = 3214touching, n = 25621stored ⁄ dense at largest0.07the rank belongs to the geometryand not to the sampling
Fig. 2 The same comparison at fourteen digits, where both rows lift and neither changes shape. The flatness is not an artefact of a lenient tolerance.
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 0.01. The admissible pair — [0, 1] against [2, 3] — needs 2, 2, 2, 2 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 3, 4, 4, 5, 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.45678902468log₂ of the points a sidecolumns above 0.01two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 322admissible, n = 2562touching, n = 323touching, n = 2565stored ⁄ dense at largest0.016the rank belongs to the geometryand not to the sampling
Fig. 3 And at two, where the admissible block is down to two columns and the touching one still climbs.

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.

Three routes to the error of a rank-k approximation of one block, at q = 0.5The upper line is q^(p+1)/(1 − q), which used four numbers about two intervals and no entry of the matrix. The middle line is the truncated expansion actually evaluated — a rank p + 1 matrix written down as a table of powers, with no decomposition anywhere in it — and it falls at -0.37 decades a column, close to the log₁₀ q = -0.30 the bound predicts. The lower line is the decomposition, which is optimal by construction, and it falls at -1.74 — 4.8 times as fast. Two of these curves share no arithmetic. What they agree on is that the error is geometric in the rank; what they disagree on is the base, by a factor in the exponent rather than a constant, and the disagreement is why a partition allocated from the bound is safe and wasteful at the same time.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹rank of the approximationrelative errorthe boundthe expansion, evaluatedthe decompositiontwo routes, one shapebound at rank 50.063expansion at rank 50.0048decomposition at rank 52.7·10⁻⁹written, decades a column0.37best, decades a column1.7one route used the matrixand the other used four numbers
Fig. 4 The expansion evaluated at 48 points a side. The three error curves are the same three curves at 192, which is the same statement from the other side.
Three routes to the error of a rank-k approximation of one block, at q = 0.5The upper line is q^(p+1)/(1 − q), which used four numbers about two intervals and no entry of the matrix. The middle line is the truncated expansion actually evaluated — a rank p + 1 matrix written down as a table of powers, with no decomposition anywhere in it — and it falls at -0.36 decades a column, close to the log₁₀ q = -0.30 the bound predicts. The lower line is the decomposition, which is optimal by construction, and it falls at -1.74 — 4.8 times as fast. Two of these curves share no arithmetic. What they agree on is that the error is geometric in the rank; what they disagree on is the base, by a factor in the exponent rather than a constant, and the disagreement is why a partition allocated from the bound is safe and wasteful at the same time.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹rank of the approximationrelative errorthe boundthe expansion, evaluatedthe decompositiontwo routes, one shapebound at rank 50.063expansion at rank 50.0048decomposition at rank 52.8·10⁻⁹written, decades a column0.36best, decades a column1.7one route used the matrixand the other used four numbers
Fig. 5 And at 192. Nothing moves, because none of the three quantities has an n in it.

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.

How many columns a decade of accuracy costs, measured and predicted, at q = 0.800The number of singular values above ε, against the number of digits ε asks for, on a 128 × 128 block between two intervals separated by a gap of 0.25. The measured curve is a straight line at 0.84 columns a decade: a digit costs the same handful of columns wherever you buy it, which is why the accuracy is a knob and not a cliff. The upper line is what the geometry alone promises — q^(p+1)/(1 − q) below ε, solved for p, using four numbers and no entry of the matrix — at 10.34 columns a decade. Both are straight and they are not the same straight: the bound is right about the shape and loose by 12.7× about the constant, which is the safe direction for a quantity you have to allocate storage from.0369121503570105140digits asked for, −log₁₀ εcolumns keptwhat the geometry promiseswhat the matrix costsa rank is a number of digitscolumns a decade0.84bound, a decade10rank at 10⁻⁸7bound at 10⁻⁸90q0.8the shape is rightand the constant is not
Fig. 6 The closest separation at which the question can be asked at all. A quarter of an interval width further in, the two clusters touch, q is exactly one, and the expansion the upper line comes from does not converge — so the figure refuses to draw it rather than drawing a bound that does not exist.

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.

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. 7 The second response, drawn: the diagonal fringed with small dense blocks, each of them a pair the test refused, and no rank on the picture above five.
A 256 × 256 kernel matrix partitioned by the weak rule, with each compressed block's rank46 blocks: 16 kept dense and 30 stored as two thin factors, whose ranks run from 8 to 12. 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 weak rule compresses every off-diagonal block there is, including the two touching halves at the top level, whose rank is the largest number on the picture and is the one that climbs as the matrix grows. The whole thing stores 24,064 numbers against 65,536 entries, and reproduces the matrix to 1.08·10⁻⁹.121210109988889988881010998888998888rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe weak partitionblocks46kept dense16largest rank12numbers stored2.4·10⁴‖A − A_H‖ ⁄ ‖A‖1.1·10⁻⁹the picture is decidedbefore a number is read
Fig. 8 And the first, where the two touching halves at the top level are compressed like everything else and carry the largest rank in the picture.

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:

n 2k ⁄ n numbers stored entries
32 0.31 320 1,024
64 0.16 640 4,096
128 0.078 1,280 16,384
256 0.039 2,560 65,536

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 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 4, 4, 4, 4 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 8, 9, 10, 11, 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 = 324admissible, n = 2564touching, n = 328touching, n = 25611stored ⁄ dense at largest0.031the rank belongs to the geometryand not to the sampling
Fig. 9 At six digits, where the admissible block is at four columns and the ratio at n = 256 is one in thirty-two.
Words moved against the block size, n = 96, M = 100A U-shaped curve on logarithmic axes. Too small a block refactors the panel too often; too large a block does not fit in the fast memory and the tiled update evicts what it is about to read. The minimum is at b = 8, which is √M − 2. The three-line count says √(M/3) = 5, which has the right scaling and the wrong constant.110¹10²10⁵block size bwords movedthe count: √(M/3) = 5measured best: b = 8words movedat the best block1.2·10⁵at b = 15.5·10⁵at b = 243.2·10⁵derived from M with no measurement, and scannedthe two agree
Fig. 10 Counting what a computation actually spends, from the cost field, which is the discipline this section is borrowing: an operation count and a memory traffic count are different numbers and only one of them is the price.

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.

Convergence factor against grid size, with 2 pre-smoothing sweepsThree curves against grid size on a logarithmic horizontal axis. Two rise towards one; the third is a flat line near a tenth.10¹10¹.³10¹.⁶10¹.⁹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰¹10².²00.250.50.751grid points nresidual reduction per stepJacobiGauss–SeidelV-cycleV-cycle spread, 8× in size0.003Jacobi at n = 1270.99work exponent, fitted0.079the dashed curve is cos(πh), Jacobi's closed formthe flat line is the whole method
Fig. 11 The oldest of the three on this site, from the iterative field: a convergence factor that does not notice how fine the grid is, and the reason a multigrid solve is linear.
The same preconditioner in one dimension and in two (ρ = 0.9)Iteration count against the number of unknowns, on a logarithmic size axis. In one dimension the preconditioned count is 7, 10, 10, 10 — flat across a factor of six in size. On square grids with the same unknown counts it is 10, 18, 20, 21, climbing, against an unpreconditioned 14, 37, 73, 115. Nothing about the construction changed.10²020406080100120unknownsiterations2D, no preconditioner2D, preconditioned1D, preconditionedone construction, two dimensions2D steps at 16 unknowns102D steps at 100 unknowns211D steps at 100 unknowns10the same averaging, the same transformand a count that no longer stops growing
Fig. 12 And the randomised field’s, where the quantity that does not appear is the dimension of the space the sketch is drawn in.

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.

Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 40 needs 12, 16, 22, 33, 53, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 3.2, 6.4, 12.7, 25.5, 50.9 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-1012301020304050log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 401 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.512cos(κr)/r at L = 853the geometry did not moveand the rank did
Fig. 13 The first of the three, which is the next essay: the same q at every point on the sweep, one kernel that does not notice the scale and one that does.
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. 14 And the second, four essays ahead: the same matrix under one permutation, and what it costs.

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.

V-cycle convergence factor against problem size, ε = 0.001Three flat curves of convergence factor against the number of unknowns on a logarithmic axis. At small anisotropy one sits near one and the others near a tenth.10²10².⁵10³10³.⁵00.250.50.751unknownsresidual reduction per cyclepointy-linesemi-yy-line spread, 4× in size1.1·10⁻⁴point at the largest grid0.97y-line at the largest grid0.03715×15, 31×31, 63×63 interior gridsflat in the size, whatever the anisotropy
Fig. 15 The closed form beside the measurement, from the field that has both. What that field can prove about its constant is what this field argues about its rank.
A randomised rank-k solve, 4 seeds a rankRelative error against the rank kept, on a logarithmic vertical axis, with a vertical bar at each rank spanning the seeds. The band is 1.68 wide at rank 8, where the method is at its worst, and 1.004 wide at rank 20, where it is at its best. The same computation on the same data returns a different answer each time.0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.7spread at rank 201best median error0.15widest where the method is worstand the bound does not say so
Fig. 16 And the other way a claim of this kind can be made honest, from the randomised field: attach a probability to it and draw the band rather than the line.

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.

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. 17 The opposite result in the field next door, from the essay that established it: the fill of a sparse factorisation grows faster than the matrix does, which is why the iterative field exists.
Numbers stored per unknown, against the size of the matrix, at 10⁻⁸The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 54, 79, 106, 133 and 50, 70, 94, 120, adding about 26 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 26 and 23 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.55, 1.42, 1.33, falling towards one and never arriving, which is what a logarithm looks like from inside.56789100108216324432log₂ nnumbers stored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5126.8·10⁴weak, n = 5126.1·10⁴dense, n = 5122.6·10⁵per doubling26‖A − A_H‖ ⁄ ‖A‖3.8·10⁻¹⁰the dense line doublesand the other two add a constant
Fig. 18 And what the flat row adds up to over a whole matrix: storage per unknown that adds a constant when the problem doubles, against a dense matrix that doubles.
The singular values of one off-diagonal block, for four kernels on the same 256 pointsTwo intervals that do not touch — [0, 1] and [2, 3] — and the 256 × 256 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 256 singular values above 10⁻⁸ out of 256, 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⁻⁸256σ₂ ⁄ σ₁0.024σ₆ ⁄ σ₁2.8·10⁻⁹the block has full rankand five useful columns
Fig. 19 The spectrum at the largest size measured, where five values sit above the eight-digit line and 251 do not.

The same null result, elsewhere

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 6, 6, 6, 6 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 11, 13, 14, 16, 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.4567890369121518log₂ of the points a sidecolumns above 10⁻¹⁰two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 326admissible, n = 2566touching, n = 3211touching, n = 25616stored ⁄ dense at largest0.047the rank belongs to the geometryand not to the sampling
Fig. 20 At ten digits, where the admissible row sits at six and is still one number across the sweep.
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 3, 3, 3, 3 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 6, 6, 7, 8, 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.456789024681012log₂ of the points a sidecolumns above 10⁻⁴two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 323admissible, n = 2563touching, n = 326touching, n = 2568stored ⁄ dense at largest0.023the rank belongs to the geometryand not to the sampling
Fig. 21 And at four, where it sits at three. The row is flat at every accuracy the block has singular values across.
Numbers stored per unknown, against the size of the matrix, at 10⁻¹⁰The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 57, 87, 118, 151 and 56, 80, 108, 140, adding about 31 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 30 and 27 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.60, 1.45, 1.35, falling towards one and never arriving, which is what a logarithm looks like from inside.56789100108216324432log₂ nnumbers stored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5127.7·10⁴weak, n = 5127.2·10⁴dense, n = 5122.6·10⁵per doubling31‖A − A_H‖ ⁄ ‖A‖4.9·10⁻¹²the dense line doublesand the other two add a constant
Fig. 22 What the flat row becomes over a matrix: numbers stored per unknown, adding a constant per doubling where the dense matrix doubles.
The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 7 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 12, 14, 16, 18, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 86,784 numbers against 79,872 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.5678910048121620log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers8.7·10⁴weak, numbers8·10⁴strong ⁄ weak1.1the better partitionis the more expensive one
Fig. 23 The touching block’s growth arriving inside a whole partition, at the accuracy where it is largest.
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 128, 184, 240, 296 at n = 64, 128, 256, 512 — 56 more per doubling, which is a logarithm. The other line is n², the entries the compression route reads. At n = 512 that is 296 products against 262,144 entries, and the representation it produces is within 7.6× 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 = 512296entries at n = 5122.6·10⁵per doubling56‖A − A_H‖ ⁄ ‖A‖1.5·10⁻⁸excess over the compression7.6no entry of the matrixwas ever read
Fig. 24 And the same shape in the construction, from the randomised field: products that add a constant per doubling against entries that square.
Multiplications in a hierarchical solve and in a dense factorisation, and where they crossBoth counted rather than estimated: the recursion carries a counter and reports what it actually did. The dense factorisation is n³/3 and rises at exactly three per doubling. The hierarchical solve rises at 2.06, 1.87, 1.66 — falling, because the cost is n log²n and its exponent is on its way to one. The two cross between n = 64 and n = 64: below it the format is the more expensive way to solve the system, at 0.61 times the dense count, and at n = 512 it is 17.5 times cheaper. Every point returns an answer at a backward error of about 1.5·10⁻⁶, so the comparison is between two ways of getting the same thing.567891010⁴10⁵10⁶10⁷10⁸10⁹log₂ nmultiplicationsdense factorisation, n³⁄3the recursion, countedwhere the format starts payingratio at n = 640.61ratio at n = 5120.057exponent, first doubling2.1exponent, last doubling1.7backward error1.5·10⁻⁶cheaper is a sizenot a property
Fig. 25 The exponent of a solve at four digits, where the ranks are small and the crossover is earliest.
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. 26 The sparsity field’s version of the growth, where the block being measured is what an elimination left on a separator.
Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 80 needs 16, 22, 33, 53, 92, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 6.4, 12.7, 25.5, 50.9, 101.9 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-101230163248648096log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 801 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.516cos(κr)/r at L = 892the geometry did not moveand the rank did
Fig. 27 And the counterweight at its sharpest, which is the next essay: a rank that grows with the size of the picture at every wavelength short enough to fit inside it.
Three routes to the error of a rank-k approximation of one block, at q = 0.5The upper line is q^(p+1)/(1 − q), which used four numbers about two intervals and no entry of the matrix. The middle line is the truncated expansion actually evaluated — a rank p + 1 matrix written down as a table of powers, with no decomposition anywhere in it — and it falls at -0.36 decades a column, close to the log₁₀ q = -0.30 the bound predicts. The lower line is the decomposition, which is optimal by construction, and it falls at -1.74 — 4.8 times as fast. Two of these curves share no arithmetic. What they agree on is that the error is geometric in the rank; what they disagree on is the base, by a factor in the exponent rather than a constant, and the disagreement is why a partition allocated from the bound is safe and wasteful at the same time.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹rank of the approximationrelative errorthe boundthe expansion, evaluatedthe decompositiontwo routes, one shapebound at rank 50.063expansion at rank 50.0048decomposition at rank 52.8·10⁻⁹written, decades a column0.36best, decades a column1.7one route used the matrixand the other used four numbers
Fig. 28 The three error curves at 144 points a side. None of the three has an n in it, which is this essay’s result stated at every rank rather than at one accuracy.

Where this goes next

0369121501122334455digits asked for, −log₁₀ εcolumns keptwhat the geometry promiseswhat the matrix costsa rank is a number of digitscolumns a decade0.55bound, a decade3.3rank at 10⁻⁸5bound at 10⁻⁸28q0.5the shape is rightand the constant is not A rank that is a number of digits Ask a kernel block for two digits and it costs two columns; ask for fourteen and it costs nine. The curve is a straight line at 0.55 columns a decade, and the bound the geometry gives is a straight line too — at 3.32, which is the same shape and six times the price. 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. 10¹10¹.³10¹.⁶10¹.⁹⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰⁰¹10².²00.250.50.751grid points nresidual reduction per stepJacobiGauss–SeidelV-cycleV-cycle spread, 8× in size0.003Jacobi at n = 1270.99work exponent, fitted0.079the dashed curve is cos(πh), Jacobi's closed formthe flat line is the whole method A rate that does not notice the size The V-cycle reduces the residual by a factor of ten a cycle at fifteen points and at a hundred and twenty-seven. Jacobi on the same four problems goes from 0.981 to 0.9978, climbing towards one. One of those is a constant and the other is an exponent, and that is the whole distinction the field turns on.

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.

AdmissibilityAsymptotic analysisDiscretisationHierarchical matrixKernel matrixLow-rank approximationModel problemNumerical rankOff diagonal rankSeparable expansion