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

A class is no longer one matrix

On a uniform grid every off-diagonal block of one width and one offset is the same matrix, so a probe that compresses one block of each class reads the whole partition's ranks and names a hierarchical matrix's cheapest leaf. On scattered points that stops being true, and the prediction was that the ranks inside a class would spread by at most one, that three blocks a class would still name the leaf everywhere, and that the probe would fail first at the highest frequency. The ranks spread by up to four. Three blocks a class still name the cheapest leaf on all thirty cells of two draws — so does one — and nothing fails at the highest frequency. The decision survives because no mean the rule compares sits close to its threshold, and scattering moved no cheapest leaf at all.
18 min read 5 figures Measured, not assumedWhose fault is itClaims that can fail

Worth reading first: The offset that moved the slope · Which pairs are allowed to be small.

Each halving reads its own width found a cheap way to choose a hierarchical matrix’s leaf size. The rule from a quarter of the leaf halves the leaf, starting from 64, while the blocks the halving creates have a mean rank below a quarter of the leaf being split — because splitting a dense block of side ss into two dense halves and two blocks of rank kk saves storage exactly when k<s/4k < s/4. The essay showed that each halving has to be read off the blocks of its own width: the decision whether to halve 32 to 16 is about the 16-wide blocks, which an 8-wide block can never stand for. And it found that on a uniform grid the probe is tiny, because a kernel that depends only on the distance between points makes every admissible block of one width at one offset from the diagonal the same matrix. One block per class of width and offset — eighteen blocks — stood for the whole partition, at under a fiftieth of the work of compressing it, and named the cheapest leaf on all fifteen cells: five frequencies of cos⁡(κr)/r\cos(\kappa r)/r, three tolerances.

It ended on the obvious weakness. “With the points drawn at random instead of on a grid, blocks of one width and offset stop being identical. The prediction with a sign is that on 512 uniformly random points the 16-wide blocks’ ranks within one class spread by at most one, so that a probe sampling three blocks a class still names the cheapest leaf on all fifteen oscillatory cells, and that it fails first at κ=1,080\kappa = 1{,}080, where a wavelength is closest to the gaps between points.”

The middle clause holds, on two draws of points rather than one. The other two do not, and the reason the middle one holds anyway is the useful part.

The same experiment, on points that are not a grid

The points are 512 draws from the uniform distribution on [0,1][0, 1], sorted, on two independent draws. The kernel and its shift are the grid’s: cos⁡(κr)/r\cos(\kappa r)/r evaluated at r=∣x−y∣+1/512r = |x - y| + 1/512, at κ=1313\kappa = 13\tfrac13, 40, 120, 360 and 1,080, truncated at relative tolerances 10−410^{-4}, 10−810^{-8} and 10−1210^{-12}. The cluster tree halves the index range at each level, as before, and the admissibility test reads the clusters’ actual positions, so the partition is the one these points give: at a leaf of four, 760 admissible blocks of widths four to thirty-two, in twenty-two classes of width and offset.

For the ground truth every leaf from 4 to 64 is built and its storage counted, on every cell of both draws — 150 builds — so the cheapest leaf is known, not predicted. Every admissible block of the leaf-4 partition is compressed, so the spread of ranks inside each class is known. And the halving rule is fed three versions of each width’s mean rank: over every block, over three blocks a class (the first, the middle and the last along the diagonal), and over one.

The leaf does not move

The cheapest leaf for cos(κr)/r on two draws of 512 uniformly random points, at five frequencies and three tolerances, and whether the width probe names it — read over every block, three blocks a class, and oneEvery block: 30 of 30. Three blocks a class: 30. One block a class: 30. Cheapest leaves by cell: draw 1, κ 40/3, ε 10⁻⁴: 8; draw 1, κ 40/3, ε 10⁻⁸: 16; draw 1, κ 40/3, ε 10⁻¹²: 16; draw 1, κ 40, ε 10⁻⁴: 8; draw 1, κ 40, ε 10⁻⁸: 16; draw 1, κ 40, ε 10⁻¹²: 16; draw 1, κ 120, ε 10⁻⁴: 8; draw 1, κ 120, ε 10⁻⁸: 16; draw 1, κ 120, ε 10⁻¹²: 32; draw 1, κ 360, ε 10⁻⁴: 16; draw 1, κ 360, ε 10⁻⁸: 32; draw 1, κ 360, ε 10⁻¹²: 32; draw 1, κ 1080, ε 10⁻⁴: 16; draw 1, κ 1080, ε 10⁻⁸: 32; draw 1, κ 1080, ε 10⁻¹²: 32; draw 2, κ 40/3, ε 10⁻⁴: 8; draw 2, κ 40/3, ε 10⁻⁸: 16; draw 2, κ 40/3, ε 10⁻¹²: 16; draw 2, κ 40, ε 10⁻⁴: 8; draw 2, κ 40, ε 10⁻⁸: 16; draw 2, κ 40, ε 10⁻¹²: 16; draw 2, κ 120, ε 10⁻⁴: 8; draw 2, κ 120, ε 10⁻⁸: 16; draw 2, κ 120, ε 10⁻¹²: 32; draw 2, κ 360, ε 10⁻⁴: 16; draw 2, κ 360, ε 10⁻⁸: 32; draw 2, κ 360, ε 10⁻¹²: 32; draw 2, κ 1080, ε 10⁻⁴: 16; draw 2, κ 1080, ε 10⁻⁸: 32; draw 2, κ 1080, ε 10⁻¹²: 32. The same leaves are cheapest on the uniform grid.draw 140/3401203601080ε = 10⁻⁴8881616ε = 10⁻⁸1616163232ε = 10⁻¹²1616323232draw 240/3401203601080888161616161632321616323232frequency κ across, tolerance down; each cell prints the cheapest leafshaded: all three probes name itscattering moved no decision
Fig. 1 The cheapest of five leaves on every cell of two draws of random points — frequency across, tolerance down — and whether the width probe names it from every block, from three blocks a class and from one. Every cell is shaded: all three name it.

The first result is about the problem rather than the probe. On every one of the thirty cells — fifteen per draw — the cheapest leaf on the random points is the cheapest leaf on the grid: 8 at the loosest tolerance for the three lowest frequencies, 16 at the two highest; 16 at 10−810^{-8} for the lowest three, 32 for the highest two; and 16, 16, 32, 32, 32 at 10−1210^{-12}. Scattering the points changes the matrix entry by entry and changes nothing the leaf decision depends on.

Storage at every leaf size relative to the cheapest, cos(κr)/r at κ = 1,080 and three tolerances: two draws of random points, solid, and the uniform grid, dashedε 10⁻⁴: draw 1 1.100, 1.026, 1.000, 1.107, 1.489; draw 2 1.098, 1.027, 1.000, 1.108, 1.497. ε 10⁻⁸: draw 1 1.174, 1.111, 1.022, 1.000, 1.163; draw 2 1.164, 1.106, 1.022, 1.000, 1.163. ε 10⁻¹²: draw 1 1.227, 1.176, 1.085, 1.000, 1.052; draw 2 1.226, 1.179, 1.088, 1.000, 1.053. The minimum falls at the same leaf as on the grid at every tolerance.11.11.21.31.41.51.6leaf sizestorage over the cheapest leaf's48163264ε = 10⁻⁴ε = 10⁻⁸ε = 10⁻¹²dashed: the uniform gridthe same minimum, scattered or not
Fig. 2 Storage at every leaf over the cheapest leaf’s, at κ = 1,080 and three tolerances: both draws of random points solid, the uniform grid dashed. The minimum falls at the same leaf on all three point sets at every tolerance.

The storage curves show how little room the decision has to move. At κ=1,080\kappa = 1{,}080 and 10−1210^{-12} the leaf of 32 is cheapest on both draws and on the grid; the leaf of 64 costs 5 per cent more and 16 costs 8 per cent more. The random points’ curves lie almost on the grid’s, a few per cent apart at each leaf, and they keep its shape — a broad minimum one leaf wide, with steep walls at the small leaves and the large. A probe needs to find that minimum, not to measure the curve, and a minimum this clear is hard to miss.

The probe names it, from three blocks or one

So the probe has an easy target, and it hits it. Fed the mean over every admissible block, over three blocks a class, or over a single block a class, the width rule names the cheapest leaf on all thirty cells. That is the prediction’s middle clause, and stronger: it held for one block a class, which the prediction did not try.

It held at κ=1,080\kappa = 1{,}080 too, where the prediction expected the first failure. The prediction’s reason was geometric — a wavelength comparable to the gaps between points — and the numbers do not support even the premise. At κ=1,080\kappa = 1{,}080 a wavelength is 2π/1080=0.00582\pi/1080 = 0.0058. The mean gap between 512 uniform points is 0.00190.0019, a third of a wavelength; the widest gaps on the two draws are 0.014 and 0.018, two and three wavelengths. So the highest frequency does have gaps wider than its wavelength, and those gaps make some blocks’ entries oscillate faster across a cluster than any grid block’s do. It does not matter, because the decision is not made on any one block.

The classes do spread

Every admissible block's rank at ε = 10⁻⁸, cos(κr)/r with κ = 360 on 512 random points, grouped into classes by width and offset from the diagonal, with each width's mean rank and the threshold the rule compares it with22 classes. Widest spread inside a class: 4-wide 1, 8-wide 3, 16-wide 3, 32-wide 1. Mean rank by width: 4-wide 3.99, 8-wide 6.16, 16-wide 8.24, 32-wide 9.29. The cheapest leaf is 32 and every probe names it.024681012rank of a block at ε = 10⁻⁸4-wide8-wide16-wide32-wideline: the width's mean · dashed: the rank at which it stops halvinga class is no longer one matrix
Fig. 3 Every admissible block’s rank at ε = 10⁻⁸ on the first draw, at the frequency on the dial, grouped into classes by width and offset: each width’s mean rank as a line, and the rank at which the rule stops halving as a dashed line. On a grid every dot in a class would sit at one height.

The prediction’s first clause fails. On a grid the dots of one class would sit on top of each other; on scattered points they do not. At κ=360\kappa = 360 and 10−810^{-8} on the first draw, the 16-wide classes’ ranks spread by three, the 8-wide by three. Turn the dial: the spread is there at every frequency, and grows with it — a class of blocks aligned by index on scattered points is a family of different geometries, some pairs of clusters a little closer, some a little wider, and an oscillatory kernel’s rank tracks the clusters’ extent in wavelengths.

The widest spread of ranks inside one class of blocks of each width, on every cell of both draws of random points16-wide classes spread by more than one rank on 18 of 30 cells, by up to 4; 8-wide by up to 3; 32-wide by up to 4. On the uniform grid every spread is zero.012345widest spread of ranks in one class4-wide classes8-wide classes16-wide classes32-wide classesdashed: the predictedspread for 16-widethe thirty cells: draw, then frequency, then toleranceon a grid every spread is zerothe prediction's mechanism fails
Fig. 4 The widest spread of ranks inside one class of each width, on every cell of both draws. The dashed line at one is the predicted spread for the 16-wide classes; on a grid every spread would be zero.

Across all thirty cells the 16-wide classes spread by more than one rank on eighteen and by up to four, at κ=360\kappa = 360 and 10−1210^{-12} on the first draw. The 8-wide classes spread by up to three, the 32-wide by up to four, the 4-wide by up to two. The smaller cluster sets the rank found an oscillatory block’s rank growing with the extent of its smaller cluster in wavelengths; on random points two clusters of sixteen indices have extents that differ from block to block by a factor of two or more, and the ranks follow. A class is no longer one matrix, and nothing about the spread is small.

What a block’s rank is following

The spread has a cause that can be measured. At κ=360\kappa = 360 and 10−810^{-8} on the first draw there are 92 admissible 16-wide blocks, with ranks from six to ten, and the clusters they join span between 2.5 and 4.4 wavelengths together. Ranked against each other, a block’s rank and its clusters’ combined extent in wavelengths have a rank correlation of 0.60; against the smaller cluster’s extent alone, 0.53. At κ=40\kappa = 40 the extents are a fifth to a half of a wavelength and the correlation is 0.58; at κ=1,080\kappa = 1{,}080 and 10−1210^{-12}, with clusters seven to thirteen wavelengths long and ranks from ten to fourteen, it falls to 0.43, because at that frequency the gaps inside a cluster matter as well as its ends.

Three earlier measurements bound what that variation can do. The size the rank does not notice found a smooth kernel’s block rank unchanged when the same geometry was sampled at four times the points, so the number of points in a cluster is not what moves it. A rank that is a number of digits found rank growing with the digits asked for at a steady rate, which is why the spread here is larger at 10−1210^{-12} than at 10−410^{-4}: every block’s rank is larger, and so is the difference between a short cluster’s and a long one’s. And the kernel with nothing to compress found the oscillatory kernel’s rank growing without limit as the picture is scaled up in wavelengths, which is the same effect at the scale of one cluster: a cluster twice as long is a block with twice as many wavelengths in it.

So the spread is not noise in the rank computation. It is the earlier finding that an oscillatory block’s rank is set by how many wavelengths its clusters span, applied to clusters whose spans now vary. On the grid every 16-index cluster spans exactly fifteen grid spacings, every block in a class sees the same number of wavelengths, and the class is one matrix; on random points a 16-index cluster spans anywhere from about half to about twice the average, and its block’s rank moves accordingly. A probe that knew the points could predict each block’s rank from its extent; a probe that does not know them samples blocks and averages, and the averaging is what has to be good enough.

Why the spread does not reach the decision

For every cell of both draws, the closest any of the rule's comparisons came to its threshold: the distance in ranks between a width's mean rank and the rank at which the rule stops halvingSmallest 0.17 at κ 120, ε 10⁻¹²; median 0.69; largest 2.67.00.511.522.53closest decision, ranks from the thresholddraw 1draw 2the thirty cells: draw, then frequency, then tolerancea decision closer than its spread could flipno decision was close
Fig. 5 For every cell of both draws, the closest any of the rule’s comparisons came to its threshold, in ranks: the distance between a width’s mean rank and the rank at which halving stops. The smallest is 0.17; the median about 0.7.

The rule compares one number per width with one threshold: is the mean rank of the s/2s/2-wide blocks below s/4s/4? The mean is over every class of that width — four to six classes — and over every block in them. A spread of three inside one class moves that mean by a fraction of three, and the classes’ errors partly cancel because some of their blocks are wider than the grid’s and some narrower.

What decides whether that is enough is the distance between the mean and the threshold. Over all thirty cells, every mean the rule tested sat at least 0.17 of a rank from its threshold, at κ=120\kappa = 120 and 10−1210^{-12} on the first draw, with a median of about 0.7 and a largest of 2.7. A probe that read one block per class drew a different mean from the full one, but never one that crossed a threshold the full mean had not. The probe survives the spread because no decision was close.

The probe that reads one block a class tests this most severely, because it averages least. At each width the rule consults, the single-block mean differs from the full mean by the average of four to six classes’ sampling errors, each of which can be as large as a class’s spread. Measured over every width each decision consulted on all thirty cells, the largest such shift is 1.2 ranks and the median 0.4. On some cells that is more than the cell’s narrowest margin — but the narrowest margin is at one width and the largest shift at another, and at no width on any cell did the single-block mean land on the other side of its threshold from the full one. The prediction’s mechanism said the probe would need classes tight to one rank; what it needed was, at every width it consults, a mean that moves less than its own distance from the line.

That is a property of these fifteen cells, and it is the same property that made the earlier essays’ probes work on the grid: the cheapest leaf is a broad minimum and the rule’s thresholds sit away from the measured means. A quarter of the leaf derived the threshold from storage, and one build tells the leaf found the ranks at different widths falling well on one side of it or the other. Scattering adds noise to the measured means; it would take noise as large as the margin at the width in question to change an answer, and on these thirty cells it never was.

What the grid was hiding

The earlier essay’s probe was sold on an exact symmetry: on the grid one block a class is not an estimate of the class’s rank, it is the class’s rank, because every block in the class is the same matrix. That made the probe look like a shortcut that depended on the symmetry, and it made the prediction look natural: break the symmetry and the shortcut should weaken, most where the geometry is most irregular relative to the kernel.

The measurement says the symmetry was never what made the probe work. The leaf decision is a comparison of an average with a threshold, made at a handful of widths, and an average over a few dozen blocks is a good estimate of itself whether or not the blocks agree. The symmetry made the estimate exact, which was more than the decision needed. On scattered points the estimate is approximate and the decision is still not close, so the answer does not change. That is a less elegant reason than the grid’s, and a sturdier one: it does not depend on the points at all, only on the margins, and the margins can be read off the probe itself. A probe that reports its means alongside its thresholds says how much it can be trusted.

What a probe of scattered points costs

The probe is cheaper than the build it replaces whatever the points. On the grid one block a class was eighteen small singular-value decompositions against a full compression’s 186 blocks at a leaf of eight; on scattered points the leaf-4 partition has twenty-two classes and one block a class is twenty-two decompositions of blocks four to thirty-two wide, against the 150 full builds this essay ran to know the answer. Three blocks a class is sixty-six. The saving does not depend on the classes being identical, which is the part of the earlier essay’s argument that did not survive: the probe was never cheap because a class was one matrix, but because a few blocks of each width say where that width’s mean sits.

Which pairs are allowed to be small built the partition from the clusters’ geometry, and on scattered points that geometry is irregular — clusters of equal index count with unequal extents. The admissibility test handles that by measuring each pair; the probe handles it by averaging. Both work here for the same reason: a uniform random sample of 512 points is irregular at the scale of a few points and regular at the scale of a cluster of sixteen, and the leaf decision is made at the second scale.

What two draws do not show

Both draws are uniform. Points with clusters and voids at the scale of a leaf — a density that varies by a factor of ten across the interval — would make blocks of one class differ in kind, not only in degree, and the margins measured here would not be expected to hold; that is the first question below. The kernel is one oscillatory family with a fixed shift. The probe’s three blocks are the first, middle and last along the diagonal, a deterministic choice; a random choice would behave the same on uniform points and is not tried. And the explanation of why the spread does not reach the decision rests on the measured margins, not on a bound relating the spread inside a class to the shift it can make in the mean.

Still open: points that cluster, and a margin that can be predicted

Points that cluster. A density that varies across the interval breaks the regularity at the scale of a cluster. The prediction with a sign is that on 512 points drawn from a density ten times higher on the left fifth of the interval than elsewhere, the cheapest leaf differs between the dense and the sparse halves of the matrix by at least a factor of two at κ=360\kappa = 360 and 10−810^{-8}, and that a single leaf for the whole matrix — whatever the probe names — stores at least 5 per cent more than the best leaf chosen separately for each half.

A margin that can be predicted. The probe’s safety rests on the distance between each width’s mean rank and its threshold. The prediction is that this distance, read off the grid’s single-block probe, predicts the scattered points’ margin to within a factor of two on at least twenty-five of the thirty cells — so that a grid probe could say in advance which cells of a scattered problem are close calls and deserve the full count.

Where this goes next

of 5 cellscheapest 32, 16-wide ≥ 85cheapest 32, 8-wide ≥ 82234567891011121323456789mean rank of the 16-wide blocksmean rank of the 8-wide blockshalving 32 → 16 does not paythe most an 8-wide block holdscheapest leaf 32cheapest 8 or 16the decision is a column, not a rowthe 16-wide blocks carry it Each halving reads its own width A hierarchical matrix's cheapest leaf is found by halving it while the blocks the halving creates have rank below a quarter of the leaf. The proposal was to probe only the near blocks of one compression at a leaf of 8, predicted to do at least as well as the whole compression. It does worse: twelve cells of fifteen against thirteen, every miss naming 16 where 32 is cheapest, because the decision between 32 and 16 turns on whether a block reaches rank 8 and an 8-wide block cannot exceed it. Read each halving off the blocks of its own width instead and the probe names the cheapest leaf on all fifteen oscillatory cells and all thirty cells of six kernels, beating even the rule with every leaf compressed, from eighteen small blocks at under one per cent of the work of the compression it replaces. k < s/4cells agreeing28cells3010⁻³10⁻²10⁻¹11distance from the threshold, relativepredicted leaf ÷ bestred: the rule's two missesboth within three per cent of the break-even A quarter of the leaf The leaf that stores a hierarchical matrix most cheaply had been read off a table of nine points, with the suggestion that it depends on the mean rank alone. Across six kernels at five tolerances — thirty cells — it does, once the mean rank is read in the right place. Plotted against the mean rank at a fixed leaf of 16, two cells a tenth of a rank apart want leaves of 8 and 16. Plotted against the rank of the blocks a halving would create, one rule — halve the leaf while that rank is below a quarter of the leaf — predicts the best leaf on 28 of the 30, and the two it misses are the two whose rank sits within three per cent of the threshold. The fractional power the last measurement expected to be rough is smoother than 1/r. 545545545455554545545545545454555555454545545545545455554545545545rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe strong partitionblocks112kept dense46largest rank5numbers stored2.7·10⁴relative compression error3.4·10⁻¹⁰the picture is decidedbefore a number is read Which pairs are allowed to be small A hierarchical representation is a partition of the matrix into blocks, and the rule that produces it reads four numbers per pair of index clusters and not one entry of the matrix. On a 256-square it yields 112 blocks, 66 of them stored as two thin factors, none of rank above five.

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.

AdmissibilityCluster treeHeuristicHierarchical matrixKernel matrixNumerical rankOff-diagonal rankStorage