A knob calibrated in residuals

A hierarchical factorisation is configured by two numbers, and a code that has to produce an answer to a stated accuracy has to know which of them to turn. One is a tolerance, applied to every admissible block when it is compressed and again after every truncation the arithmetic performs. The other is a leaf size: how few unknowns a block has to hold before it is stored densely instead of being split again.

Both of them change the answer. Neither of them is named in the units the caller cares about, which are the units of the residual. So the practical question is not what the two parameters mean but whether they separate — whether one of them can be set from the machine and the other from the accuracy required, with no term connecting them.

That question is answered here on a grid rather than on a line. Four leaf sizes, three matrix sizes, five tolerances each: sixty formatted Cholesky factorisations of the same kernel, every one of them checked against a dense reference. The answer is nearly the clean one, and the two places it is not clean are both visible only because the grid has a second axis.

The leaf moves the truncation count by a factor of forty-nine #

The number of approximate operations inside the recursion is not something anybody sets. Every Schur update is a low-rank addition pushed down the tree, it reaches every admissible block below it, and each of those is truncated back. So the count is a consequence of the shape of the tree, and the leaf size is what fixes that shape.

At 256 unknowns with a leaf of 64 the tree is two levels deep and the factorisation performs two truncations. At a leaf of 8 it is five levels deep and performs ninety-eight. Same matrix, same tolerance, forty-nine times as many approximate operations — which is the reason the essay that first measured this cost was worth writing, because the received warning about formatted arithmetic is that a count like that has to show up somewhere.

The count is worth stating exactly, because it turns out to be a function of one number rather than of two. Writing the depth of the tree as the number of levels between the root and a leaf, the twelve configurations measured here produce six distinct counts — 0, 2, 10, 34, 98 and 258 at depths of one through six — and each of those counts appears at every size that can reach that depth. Two hundred and fifty-six unknowns with a leaf of 16 and five hundred and twelve with a leaf of 32 are both four levels deep, and both perform exactly thirty-four truncations. One hundred and twenty-eight with a leaf of 8 makes it three configurations at the same count, across a factor of four in the size of the matrix.

The closed form the six counts satisfy is (L − 2)·2ᴸ + 2 at depth L, exactly, at every one of the six depths. It is a statement about the tree and not about the arithmetic: the count of admissible blocks touched by the Schur updates of a two-way recursion, and nothing in it knows what the entries are. That is worth having because it means the count can be predicted before anything is factorised, which is the opposite situation from an accumulation whose length is a parameter of the experiment.

And it does not move the ranks at all #

The second column of the figure is the one that decides the storage, and it is the surprise. Across all four leaf sizes at 256 unknowns the ranks the blocks take are 4, 7, 9, 12, 14 — the same five integers, one per tolerance, at a leaf of 8, of 16, of 32 and of 64. Forty-nine times as many truncations, and not one of them changes what any block keeps.

The mechanism is structural rather than numerical, and it is worth naming because it explains why the null result is exact rather than approximate. The largest rank anywhere in the tree is attained at the topmost admissible block, which is the coupling between the first half of the unknowns and the second half. That block exists at every leaf size, because the first split of the recursion happens before the leaf size is ever consulted; it is the same block, of the same dimensions, holding the same entries, compressed at the same tolerance. A smaller leaf adds blocks below it, and the blocks below it are smaller and have lower ranks. Nothing a deeper tree does can raise the maximum, and the measurement says nothing lowers it either.

So the leaf size is not merely accuracy-neutral in the residual, which was the earlier finding. It is neutral in the ranks, which is a stronger statement and a more useful one, because the ranks are what a storage estimate is built from. A code sizing its buffers from a sample factorisation at one leaf can carry that number to another leaf unchanged. What it cannot carry is the number of blocks, which is what the partition-against-storage trade is about, and which moves in the opposite direction from the dense fringe.

This is also the sense in which a rank here is not a knob at all. Rank is a decision when a threshold is laid across a decaying sequence, and the decision is made by the tolerance; the leaf size is not in that sentence anywhere.

The ranks belong to the problem, not to either knob #

If the ranks were a property of the format they would move when the format moved, and they do not. The remaining possibility is that they are a property of the matrix, and the third axis of the grid is what tests it.

Halving the matrix takes the ranks from 4, 7, 9, 12, 14 to 3, 6, 8, 10, 12. Doubling it takes them to 4, 7, 10, 13, 16. Those are three different columns of numbers for one parameter that neither knob controls, and they move in the direction the geometry says they should: the top-level block gets larger, its singular values decay at the same rate against a longer sequence, and the tolerance cuts it further along.

The rate is modest and it is not constant across the sweep. At the tightest tolerance measured the maximum rank runs 12, 14, 16 for a fourfold change in the number of unknowns — two columns per doubling. At the loosest it runs 3, 4, 4, which is one column across the whole range and then nothing. So the growth is logarithmic in the size and its constant depends on the tolerance, which is the same shape the exchange rate between digits and columns measures on a single block and at a lower rate, because the number here is a maximum over a tree of blocks rather than one block’s own count.

The honest reading of the grid is therefore not that two knobs partition every quantity between them. It is that three quantities are in play and only two of them are set by a knob. The leaf sets the shape of the tree and the truncation count; the tolerance sets the accuracy; and the ranks are set by the matrix, with the tolerance choosing where along the matrix’s own decay to cut. A code that treats the rank as something it can configure has misread which of the three it is holding — and that misreading is exactly what the refusal at the foot of this essay is about.

The constant that makes the tolerance quotable #

A slope of one is necessary and it is not sufficient. It says a decade in buys a decade out; it says nothing about where the line sits, and a caller asking for a residual of 10⁻⁸ needs the offset as well as the slope.

Measured over all sixty configurations, the residual is smaller than the tolerance at every one of them, and the ratio between them lies between 0.049 and 0.24. That is a factor of five across the whole grid, which is not a calibration. It becomes one when the two ends are separated. At the three tightest tolerances the ratio lies between 0.077 and 0.15, a factor of two; at the two tightest it lies between 0.091 and 0.12, a factor of 1.3 across a twelve-fold spread of trees and a fourfold spread of sizes.

So the rule a code can act on is narrow and it is real: at the accuracies a formatted factorisation is actually run at, ask for a residual, divide by ten, and compress to that. It is good to thirty per cent at 10⁻⁸ and 10⁻¹⁰, and it degrades to a factor of five by the time the tolerance has been loosened to 10⁻⁴ and 10⁻². That degradation is not a defect of the format. A loose tolerance cuts a block after two or three columns, where the decay is steep and the discarded tail is a coarse function of where the cut fell, so the constant is being read off a sequence with almost no terms in it — the same reason a threshold laid across a decaying sequence becomes a decision rather than a measurement when there are few terms to decide between.

This is what the essay’s title is about. A tolerance that is only related to the answer by a slope is a parameter of the method; a tolerance related to the answer by a slope and a constant is a parameter of the problem, quoted in the units the caller asked in. That is the property a stopping rule written in the units of the answer has by construction and that this one has by measurement, and it is the whole difference between a number a code can set and a number a code has to tune.

Where the leaf does reach into the accuracy #

The separation above is stated as though it were exact, and there is one place on the grid where it is not.

Each figure carries a second comparison alongside the residual: the error the representation itself commits, before any factorisation is performed. The ratio of the one to the other is the honest measure of what the approximate arithmetic cost, and over most of the grid it sits below one — the factorisation’s residual is smaller than the error of the object it factorised, which is the result the accumulation question turned on.

At a tolerance of 10⁻⁴ that ratio rises above one, and it does so in a pattern the single-size sweep could not have read. At a leaf of 8 it reaches 1.73, 1.78 and 1.67 at the three sizes; at a leaf of 16 it reaches 1.79, 1.83 and 1.71. At a leaf of 32 and at a leaf of 64 it never exceeds 1.00 at any size and at any tolerance on the sweep.

That last comparison is the one the grid exists for. Thirty-four truncations at a leaf of 16 produce the excursion and thirty-four truncations at a leaf of 32 do not, so the excursion is not a function of the count. Nor is it a function of the size: it appears at all three sizes at the small leaves and at none of them at the large ones. It belongs to the leaf, which is the one parameter this essay has so far argued has no accuracy term in it.

What it is, is what the figure names: at 10⁻⁴ the tolerance falls between two singular values of one block, and the rank it selects is a rounding of a decision rather than a measurement of a decay. A deeper tree has more blocks, more of them small, and a small block’s spectrum has few terms and coarse gaps — so the chance that the tolerance lands inside a gap rather than on a slope rises with the depth. It appears at a looser tolerance than the ones on either side of it for the same reason, because that is where the gaps are wide enough to fall into.

Two things bound how much this matters. It is a movement in the ratio column and not in the residual column: at 10⁻⁴ and a leaf of 16 the residual is 2.2·10⁻⁵, comfortably inside the tolerance asked for, and the calibration above is untouched. And it is bounded by a factor of two rather than by nothing, across a range of trees that spans the whole grid. The correct statement is therefore not that the leaf is accuracy-neutral but that it is neutral in the residual and not in the margin — a code quoting a residual is safe, and a code claiming that a formatted factorisation is never worse than the representation it was performed on has to say at which leaf, which is a distinction a backward error stated as a bound makes routinely and this field had not needed until now.

The same question one level down #

Everything above is about a factorisation. The representation underneath it has the same knob and a different constant, and the two are worth putting side by side because the direction of the offset is not the one a reader would guess.

Compressing a matrix and never factorising it, the obtained error is 0.028 of the tolerance for a 1/r kernel and 0.033 for log r on the identical partition — a factor of about thirty below what was asked. Factorising inside the format, the residual is about a tenth of the tolerance. The factorisation is therefore closer to the tolerance than the representation is, by a factor of three, and it should be: the residual is measured after the approximate arithmetic has been performed, and the representation’s number is measured before it.

The two constants are not the same object and the difference between them is not a defect in either. A per-block tolerance is applied against each block’s own largest singular value and the error is reported against the whole matrix’s norm, so the offset is how much of the matrix’s mass lives off the diagonal, which is a property of the kernel rather than of the partition — which is what makes the two curves in that figure differ at all, since the partition is the same one. What the pair establishes is that both numbers are constants: neither of them drifts across ten decades, so both can be quoted, and neither of them is one, so neither can be omitted. That is the answer to the question a bare tolerance leaves open, asked twice on the same object.

The refusal #

The claim under test is one that reads as a definition and is not: that a truncation returns the rank it was asked for.

It is fed a rank-three object and asked to truncate it to rank eight. The result has rank three, because a truncation can only discard, and the assertion that it has rank eight fails. That is the same shape as the mistake this essay is written against. A rank is not a setting; it is what the object turns out to have once a tolerance has been laid across it, and asking for more columns than the decay contains produces nothing — exactly as asking for a different leaf size produced 4, 7, 9, 12, 14 four times over.

The refusal is published rather than asserted in a sentence because it is the boundary between the two readings of the format’s parameters. A code that believes the rank is configurable will size its storage from the number it asked for; a code that has run this will size it from the number the matrix returns, which is the number all twelve trees agree on at a given size and tolerance, and which is the only one that appears in a residual.

What follows for anything that uses the format #

A leaf size can be chosen from the machine. It sets the depth, the truncation count and the size of the dense fringe, and it does not set the ranks or the residual. The trade is storage against locality, and it is the same kind of decision as a block size fitted to a fast memory — a machine parameter with no accuracy term, once the margin caveat above is on the record.

A tolerance can be quoted to a caller. Slope 1.022 to 1.046 across twelve trees, and a constant of about a tenth at the accuracies that matter. That is what makes it a knob rather than a tuning parameter, and it is what the site’s rule about printing a residual under every decomposition is for.

A storage estimate needs the size and not the leaf. The ranks moved with the number of unknowns and stood still under the leaf, so the estimate scales with the problem, not with the partition — which is the other half of what an admissibility test buys, where a well-separated block’s rank does not notice the sampling either.

And the crossover argument is unaffected by either. Whether the format is worth using at all is a question of where the count of multiplications crosses a dense factorisation’s, and neither of these two parameters moves the accuracy that argument is conducted at. That is the practical value of a clean separation: the cost argument and the accuracy argument can be settled independently, on the same object, without either of them having to quote the other’s parameter.