The offset that moved the slope

A hierarchical representation is chosen for one number, and that number is not its accuracy. Any format can be pushed to any accuracy. What this one is for is the rate its storage grows at: a constant added per doubling of the problem rather than a doubling of the storage. That rate is what a memory budget is written against, and it is the whole reason to accept a cluster tree, an admissibility test and a truncation in place of an array.

The rate is usually attributed to the geometry. Two knobs go into a representation: the rule that decides which pairs of index clusters may be stored as two thin factors, and the tolerance that decides how thin. The natural reading gives one number to each. The partition, being geometry, sets the slope of storage per unknown against log₂ n; the tolerance, being a truncation applied inside blocks the partition has already chosen, sets the offset — where the curve starts, not how fast it climbs.

That reading has a mechanism behind it rather than being careless. The admissibility rule reads four numbers per pair of clusters and not one entry of the matrix, so it cannot know what tolerance the blocks will be truncated at, and the block counts confirm it: 16, 46, 112 and 250 blocks at the four sizes measured, identical at every one of seven tolerances, of which 6, 24, 66 and 156 are compressed. Nothing about the geometry moves when the accuracy does, and the offset moves for an equally plain reason — a tighter tolerance keeps more columns in every block, so every curve lifts. Both of those are true. The conclusion drawn from them is not.

The claim, stated so it can fail #

The eight-digit setting above is the one this collection usually draws. The strong partition stores 54, 79, 105.5 and 132.75 numbers per unknown at 64, 128, 256 and 512 unknowns; the weak one 50, 70, 94 and 120. Both add a constant per doubling, which is what a logarithm looks like from inside, and the constants are 26.25 and 23.33.

The separable reading makes a prediction about those two constants. It says the slider should not move them at all. The partition is unchanged — the same 250 blocks, the same 156 compressed — so the quantity the partition owns should be unchanged with it, and the whole effect of a tighter tolerance should be a vertical lift: every point higher by the same amount, the new lines parallel to the ones already drawn.

That is a prediction with a number in it, and it is measured at seven tolerances rather than argued. The sweep runs 10⁻², 10⁻³, 10⁻⁴, 10⁻⁶, 10⁻⁸, 10⁻¹⁰ and 10⁻¹² on the same points, the same kernel, the same leaf size of sixteen, changing one argument and nothing else.

The increment does not stay anywhere. The strong partition’s runs 10.9, 12.6, 16.0, 21.1, 26.3, 31.4 and 36.5 numbers per unknown per doubling across those seven tolerances — a factor of 3.36 between the ends. The weak partition’s runs 7.3, 10.7, 13.3, 18.0, 23.3, 28.0 and 32.0, a factor of 4.37. The knob that was supposed to move the offset moves the slope by a factor of three, monotonically, with no setting at which the effect flattens.

The other half of the claim fails in the same direction. Holding the tolerance at 10⁻⁸ and switching the partition instead — the knob that supposedly owns the slope — moves the increment from 26.25 to 23.33, which is twelve and a half per cent. The knob assigned the slope moves it by an eighth; the knob assigned the offset moves it by a factor of three.

The loosest setting the sweep carries #

Two digits is not a straw man. It is the accuracy a hierarchical representation is run at when it is being used as a preconditioner rather than as a representation, where the object only has to be close enough to steer an iteration.

At that setting the strong partition is storing almost nothing but its dense fringe. Its largest rank anywhere is 2, its mean rank is 1.67, and 40 of the 45 numbers per unknown at n = 64 are entries of dense leaf blocks written out one by one. The curve climbs by 10.9 per doubling to 77.6 per unknown at 512 unknowns, against the dense matrix’s 512 — a factor of 6.6 saved, for a representation accurate to 6.8·10⁻⁴ relative in the Frobenius norm.

The weak partition is cheaper still, at 28, 34, 42 and 50, because it has no fringe worth the name: 16 numbers per unknown in leaves at every size, that being the leaf size, and everything else compressed at ranks of 3 and 4. It is the cheaper of the two at every size measured, by a factor of 1.55 at n = 512 — the widest the two curves ever get.

Neither total is the point. The point is that the increment per doubling here, 10.9 and 7.3, is the smallest value either partition takes anywhere in the sweep, and the bottom of a range is a useful place to start when the reading under test predicts the range has no width. One thing the two-digit picture does settle in that reading’s favour, and it should be conceded: the ordering of the two partitions never changes, the strong one costing more at all seven tolerances and all four sizes. So the geometry does own something stable. It owns which curve is on top. It does not own the growth rate, which is the number the format was chosen for.

And the tightest #

Twelve digits is the other end of what the arithmetic supports, and the picture there is a different picture rather than the same one shifted. The strong partition’s four points are 60, 94, 131 and 169.5 numbers per unknown — higher than the two-digit run by 15, 37.5, 63.75 and 91.875, a lift six times larger at the right-hand end than at the left, which is exactly what a vertical shift is not. A curve lifted by a constant keeps its slope. This one has had its slope multiplied.

The mechanism is visible in the ranks. The strong partition’s largest rank anywhere is 7 at twelve digits against 2 at two, and its mean rank is 6.67 against 1.67 — four ranks bought with ten decades of accuracy, which is 0.50 ranks a decade, close enough to the 0.554 columns a decade a single off-diagonal block charges that the whole-matrix rate is plainly the per-block rate summed up. What the whole matrix adds is the multiplier: each of those ranks is paid for once per compressed block, and the number of compressed blocks grows with the problem. A per-block cost that rises with the tolerance is a slope that rises with it too.

The left-hand end carries a coincidence worth recording. At n = 64 and twelve digits both partitions store exactly 3,840 numbers, 60 per unknown, and the two lines begin at the same point; they separate again immediately, 94 against 88 at the next doubling. Nothing follows from it except this: at twelve digits the two partitions have the same offset and different slopes, which is the opposite arrangement to the one claimed.

Seven settings, and the rate is monotone #

Two ends make a factor and not a law. The full sweep is the law, and it is a straight one.

Read down the first column and the increments between consecutive rows are 1.71, 3.42, 5.13, 5.13, 5.13 and 5.13 — which is 2.5625 numbers per unknown per doubling for every decade of accuracy, once the sweep is past its two loosest rows where the rank is quantised too coarsely for the rate to show. Ten decades add 25.6 to a slope that started at 10.9, and that is the factor of 3.36 restated as a rate. The weak column gives 2.47 per decade over the same range: the two are within four per cent of each other, which is the sharpest available statement that this belongs to no one partition rule. Both geometries hand the same fraction of their growth rate to the accuracy knob.

Where the slope actually comes from #

The table says the rate moves. Splitting the storage into its two parts says why, and the split is clean enough to be an identity rather than an explanation.

Every representation here stores two kinds of thing: dense leaf blocks, written out entry by entry, and compressed blocks, written as two thin factors. The first kind is decided entirely by the partition, and the numbers say so. The strong partition’s dense storage is 40, 44, 46 and 47 numbers per unknown at the four sizes — the same four numbers at every one of the seven tolerances, because a dense block is stored exactly and a tolerance has nothing to truncate in it. They contribute 2.33 per doubling, and that is the entire contribution the geometry makes to the growth rate. The weak partition’s dense storage is 16 per unknown at every size and every tolerance, contributing exactly nothing.

Everything else is the compressed part, and it is proportional to the rank to a degree that leaves no room for a second effect. The strong partition’s low-rank storage per unknown at n = 512 runs 30.6, 49.0, 85.75 and 122.5 at 10⁻², 10⁻⁴, 10⁻⁸ and 10⁻¹², and its mean ranks over the same four settings run 1.67, 2.67, 4.67 and 6.67. Divide one by the other and the answer is 18.375 four times, to every digit computed. That part’s contribution to the slope divides by the mean rank to give 5.125, at all seven tolerances. So the strong partition’s growth rate is

slope = 2.333 + 5.125 · (mean rank)

and it reproduces all seven measured values: 2.333 + 5.125 × 4.667 is 26.25, the eight-digit reading to the last digit drawn.

That identity is the finding stated as algebra. The partition sets a constant and a coefficient; the accuracy sets what the coefficient multiplies. A reading that assigns the slope to the geometry is right about 2.333 of it — 21 per cent of the slope at two digits, falling to 6.4 per cent at twelve — and wrong about the rest, and the rest is not a correction term but between 79 and 94 per cent of the number.

The mistake is easy to make because both halves of the reasoning behind it are sound. The partition really is computed without reference to the tolerance, and the rank really is a per-block quantity fixed by the tolerance — a block’s rank barely notices how large the block is, five columns at 32 points a side and five at 256. What the reasoning misses is that the number of blocks carrying that rank is the thing that grows. Fixing a quantity per block does not fix its contribution per unknown.

What ten decades of accuracy cost #

A slope is a statement about a picture; what a code pays is a statement about a size, and the two diverge in a way that decides how an experiment should be read.

At 64 unknowns, tightening from two digits to twelve takes the strong partition from 45 numbers per unknown to 60: 33 per cent more storage for ten decades of accuracy, which sounds like a bargain and is one. At 512 unknowns the same ten decades take it from 77.6 to 169.5, which is 118 per cent. The weak partition is harsher at both ends: 114 per cent at n = 64 and 212 per cent at n = 512.

The exchange rate between accuracy and memory is therefore not a number. It is a function of the size, and it rises because the accuracy is in the slope rather than in the offset. A code that measures the cost of a digit on a small test problem and carries the figure to a refined one has measured the wrong quantity, and the error grows with exactly the parameter refinement moves.

That inverts a shape this collection meets everywhere else. Cost curves against accuracy usually get worse as the digits are demanded, and the one method whose price per digit halves each time it is paid is remarkable for being alone. Here the price per decade is nearly flat in the tolerance — 2.56 per doubling per decade, the same for the eleventh decade as for the third — and steep in the size instead. Nor is the tolerance free to choose: when the representation is solved with, it is the backward error the answer will carry, at a slope of one over ten decades. So the accuracy is fixed by the application and the size by the discretisation, and the two multiply into a memory figure neither predicts alone.

The exponent a fit returns is not the format’s exponent #

There is a second way the moving slope reaches a reader, and it is quieter, because it arrives looking like a measured asymptotic.

Fit a power law to the four totals — the obvious thing to do with four sizes and a storage column — and the strong partition returns n^1.26 at two digits and n^1.50 at twelve. Between consecutive sizes the local exponents are 1.33, 1.25 and 1.21 at the loose end against 1.65, 1.48 and 1.37 at the tight one. Both sets fall towards one, which is the logarithm showing through, and neither has arrived.

Neither exponent is the format’s: the asymptotic statement is n log n against n log² n, and no power between one and two is a claim about either. But a code reporting that its storage scaled as n^1.26 has reported a number that would have been 1.50 had the tests been run at the tolerance the production run uses, and nothing in the fit says so — the residuals are small either way. That is the same hazard the crossover between the two partitions carries, arriving one level up: there a measurement at the largest affordable size reported an ordering that reverses two doublings past the axis, here a measurement at a convenient tolerance reports a growth rate a third of the way to being right.

Where the curve stops being worth having #

Every claim here is worth pushing until it fails, and this one fails at a corner of the sweep that is on the page rather than beyond it.

At twelve digits and 64 unknowns the strong representation stores 3,840 numbers. The matrix has 4,096. The whole apparatus — a cluster tree, an admissibility test, a truncated factorisation of every admissible block — has saved six per cent, and has introduced an error of 7.4·10⁻¹⁴ the dense array does not have. The weak partition stores the same 3,840 at that corner.

The corner is the moving slope again, read as a break-even. The share of the dense matrix the strong representation occupies at n = 512 is 15 per cent at two digits, 19 at four, 26 at eight and 33 at twelve; at n = 64 the same four settings read 70, 75, 84 and 94 per cent. The tolerance decides how large the problem has to be before the format earns its keep — a consequence the separable reading cannot produce at all, since an offset lifting every point equally would move a break-even by a fixed amount rather than scaling it.

So the honest scope is narrower than the format’s usual advertisement. The growth is a logarithm at every tolerance measured, which is why the solve built on the representation overtakes a dense factorisation somewhere between 64 and 128 unknowns. What does not survive is the idea that the logarithm’s coefficient belongs to the geometry, and with it the idea that a storage figure measured at one accuracy can be rescaled to another.

The control, where there is no curve to move #

A sweep that moves a number in every run needs a case where the same sweep moves nothing, or the conclusion is about the instrument. There are two here, and they fail differently.

The first is the same matrix under a symmetric permutation. Renumbering the points destroys the geometry the admissibility test reads without changing anything a norm can see — κ is 20.8802 both ways to eight digits — and the storage curve ceases to exist rather than tilting. No pair is admissible at any size, so the strong partition stores the matrix exactly, 16,384 numbers at n = 128, and the rule with no test to fail compresses every off-diagonal block regardless and stores 28,096, at ranks up to 57 out of a possible 64.

The second control keeps the numbering and removes the kernel. Fill the same matrix with independent normal draws, run the same partition at the same tolerance, and the representation stores 27,136 numbers at n = 128 against the matrix’s 16,384 — a ratio of 1.656, where the kernel matrix on the same points stores 10,112. Its storage per unknown at 64, 128 and 256 is 88, 212 and 466, growing faster than the dense line rather than slower.

And the tolerance does nothing to it. Those three sizes read 88, 212 and 466 at eight digits and 88, 212 and 466 at twelve, identical, because there is no decaying tail for a truncation to cut: every column survives every cut and the error is 2.2·10⁻¹⁶ at any setting. Only at two digits does anything move, and then by two per cent. This is the block that is neither sparse nor low rank taken to a whole matrix. The accuracy moves the slope only where there is a spectrum to truncate, and the spectrum belongs to the kernel and the numbering rather than to the format.

What follows for a code that has to choose both #

A storage budget must be quoted with its tolerance, and cannot be rescaled. A figure of 26 per cent of dense at 512 unknowns is a fact about 10⁻⁸ and about 512; the same representation at 10⁻¹² occupies 33 per cent, not because the offset moved but because the increment per doubling did, so the discrepancy widens with every refinement.

The two knobs are chosen together or neither is chosen. Picking a partition on asymptotic grounds and then a tolerance on accuracy grounds treats them as independent, and the slope identity says they are not. This is the coupling an ordering imposes on a sparse factorisation’s memory, where four orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries and the one with the better asymptotics is not the winner.

A small experiment prices the wrong exchange rate. Ten decades cost 33 per cent at 64 unknowns and 118 per cent at 512, so an experiment sized for one afternoon understates the cost of a digit by roughly a factor of three, and understates it further the more the production problem is refined.

Where the growth is not a logarithm, none of this applies and the failure is worse. An oscillatory kernel’s ranks grow with the scale of the picture and never stop — twelve, sixteen, twenty-two, thirty-three, fifty-three — so the mean rank in the identity above is itself a function of n and the curve is not straight against log₂ n at any tolerance.

And storage is one resource among several. Trading memory for something else is a move this collection makes elsewhere — four copies of the data against the traffic between processors — and every such trade is priced in whichever resource the figure happens to plot.

The refusal #

The claim under test is the one seven runs on one kernel tempt a reader into: that the storage growth measured here is a property of the format and the accuracy it is run at.

It is marked false, and the refusal is the noise matrix. The assertion that the same partition at the same tolerance compresses a matrix of independent draws below a quarter of its dense size is fed exactly that matrix, and it fails at 1.656 — sixty-six per cent larger than the array it was compressing. Nothing about the format changed and nothing about the tolerance changed, and the growth went from a logarithm to worse than a doubling.

Which is the boundary of everything above. The slope belongs to the rank, the rank belongs to the kernel and the numbering, and the format is the machinery that reads them. The tolerance decides how much of the available decay is used, and that is why it reaches the slope; where there is no decay it decides nothing at all.