The count that is not the budget

A factorisation carried out inside a low-rank format performs a number of approximate operations that nobody selected. The recursion is the textbook one, every step of it stays in the format, and the only approximate step in the whole of it is the Schur update: a rank-k addition pushed down the tree, which reaches every admissible block underneath and truncates each of them back. Nothing in the code takes that number as an argument. It falls out of how deep the tree is.

The number is large. On 256 unknowns a tree one level deep performs none at all and a tree five levels deep performs ninety-eight, and the received reading of formatted arithmetic says that a difference of that size has to appear somewhere in the answer. Each truncation commits an error of the size of the tail it discards; a hundred of them commit a hundred such errors; and the accuracy of the result is therefore something nobody can bound tightly.

The quantity that settles it is a ratio rather than an error. A formatted factorisation is performed on an object that is already an approximation — the representation commits its own error before anything is factorised — so the honest question is not how large the residual is but how it compares with the error of the matrix it was computed from. If the truncations accumulate, the residual outruns the representation and the ratio climbs with the depth. If they do not, the ratio stays put. That number is measured here at every accuracy the format is usable at, and it is not one number but thirty.

The count is a property of the tree and of nothing else #

The five counts are 0, 2, 10, 34 and 98, at leaf sizes of 128, 64, 32, 16 and 8. A shallow tree performs few because it has few admissible blocks to reach; a deep one performs many because a Schur update at the root touches every block in the right subtree, at every level, and the deepest levels hold most of the blocks. The first row is the control that makes the rest legible: a tree of one level has no admissible block below the split, performs no truncation whatsoever, and its residual is therefore the representation’s error exactly, to fourteen digits.

What is worth stating carefully is that those five integers do not move when the accuracy does. At 10⁻¹², at 10⁻¹⁰, at 10⁻⁸, at 10⁻⁶, at 10⁻⁴ and at 10⁻², the counts are 0, 2, 10, 34 and 98 — the same five numbers, unchanged across ten decades. The tolerance decides how many columns each truncation keeps, and the tree decides how many truncations happen; the two questions are disjoint, and the count is settled before a single entry of the matrix has been looked at.

That is what separates this measurement from the two it sits between. The essay that first priced a chain of these truncations built a synthetic sequence of rank-four additions and made the chain length its axis, which is the shape the standard warning is written in and is not the shape a real factorisation has. The grid that sweeps the leaf size at fixed tolerances asks which of the format’s two parameters sets which quantity, and answers it by moving the leaf. Here the leaf is held across the whole width of each figure and the accuracy is what moves, one decade at a time, which is the only axis on which the received worry can be tested at the scale it is stated at: the claim is not that a hundred truncations are harmless at one tolerance but that they are harmless wherever the cut is made.

The ratio belongs to the leaf, and barely notices the accuracy #

Two adjacent decades produce five ratios that agree to within five points in the last place, on curves that themselves have moved by a factor of two hundred. That is the first sign of what the sweep turns out to be about, and the full table makes it plain.

Read down a column and the numbers hardly move. At a leaf of 8 the ratio takes the values 0.853, 0.864, 0.812, 0.847 and 0.831 across the five well-behaved rows — a spread of five points over ten decades of tolerance. At a leaf of 64 it takes 0.952, 0.934, 0.930, 0.961, 0.951 and 0.954, a spread of three. Read across a row and it moves from 1.00 to about 0.85, every time.

So the ratio is very nearly a function of the leaf size alone, and the tolerance — which moves both curves by ten orders of magnitude — moves the relation between them by a few per cent. That is a stronger statement than the null result it contains. It is not merely that the truncations fail to hurt the answer at one accuracy; it is that changing the size of what every one of them discards by a factor of 10¹⁰ leaves the comparison between the factorisation and its own input where it was.

And the direction of the movement across a row is the wrong one for accumulation. More truncations give a smaller ratio, monotonically, at four of the six tolerances. A deeper tree compresses more of the matrix, so its representation error is larger; the factorisation of that more heavily approximated object has a residual in proportion, and the truncations inside the recursion contribute something below the level this measurement can resolve.

Where the deeper tree buys nothing, and still costs nothing #

The tightest accuracy is where the sweep does something none of the other five do, and it is worth having on the record because it is the cleanest available form of the whole result.

At 10⁻¹² the representation error at a leaf of 16 is 1.502323·10⁻¹³ and at a leaf of 8 it is 1.502325·10⁻¹³. Those are the same number. The extra level of the tree has compressed four times as many blocks and has bought no additional error at all, because at that tolerance the small blocks near the diagonal are being kept to essentially their full rank and the compression is doing nothing to them. The residuals for the two rows are 1.281412·10⁻¹³ and 1.281730·10⁻¹³ — a difference of two parts in ten thousand.

Those two rows differ by sixty-four approximate operations and by nothing else. The matrix is the same matrix, the tolerance is the same tolerance, the object being factorised is the same object to six significant figures, and one of the two factorisations truncates thirty-four times while the other truncates ninety-eight. If a truncation carried a cost proportional to the tail it discards and those costs summed, the deeper row would be worse by something. It is worse by 0.02 per cent, which is the scale at which the measurement itself is uncertain.

This is also where the format’s own economics stop working, and the two facts are the same fact. A deeper tree that compresses nothing is spending storage on factors that are as large as the blocks they replace, which is why the question of which pairs of index sets are allowed to be small is prior to any of this: a block that is not genuinely low rank has nothing to give a truncation, and a tree built of such blocks is a dense matrix with a bookkeeping overhead.

And at the other end, where every truncation is discarding a per cent #

The opposite extreme is the one the standard warning ought to be about, because it is where an individual truncation is doing something a reader can see.

At 10⁻² the largest off-diagonal rank anywhere in the tree is four. Every admissible block is being held in four columns, and every one of the ninety-eight truncations inside the deepest factorisation is taking a sum of two such blocks — a rank-eight object, exactly — and throwing away half of it. The discarded part is not a rounding and it is not noise: it is a per cent of the block, committed once per operation, ninety-eight times over.

The ratio at that tolerance and that depth is 0.83. It is not merely below one, it is below one by the same margin as the row where each truncation is discarding a tail at 10⁻¹². Nothing about the size of the individual error reaches the comparison.

That is the point at which the number stops being a null result and becomes a statement about what kind of quantity is being accumulated. The site has three unrelated accumulations measured against their bounds — a long sum, three thousand rotations, a residual recurrence — and all three grow like square roots against bounds that are linear. This one does not grow at all, and the reason is not that the errors cancel. It is that the running object after m truncations is close to the best low-rank approximation of what it should have been, so the error is a property of the target rather than of the route, and the count of steps taken to reach it does not appear.

What one of them actually throws away #

A count is only alarming if what is being counted is expensive, so the individual operation is worth a figure of its own. A rank-k block plus a rank-k block is a rank-2k block, exactly — concatenate the two column factors, concatenate the two row factors, and the wide pair is the sum with nothing approximated — and the truncation back to rank k is what keeps the format a format.

At rank six the twelve singular values of the sum run from 1 down to 0.444, and the largest of the six that go is 0.707 of the largest of the six that stay. None of them is small. Truncating costs 57.8 per cent of the block, and the same figure prints the best any rank-six object could have done, which is 57.8 per cent as well. The two agree because the cut is taken through the factors and is the best approximation there is — the discarded tail is the smallest error any object of that rank could have committed, which is what makes the comparison in this essay one against an optimum rather than one against another implementation.

So the operation being counted is not cheap. It discards more than half of what it is handed, and it does that ninety-eight times inside the deepest factorisation on the sweep, and the answer is indistinguishable from the one produced by a factorisation that does it none. Whatever those ninety-eight operations are doing, they are not doing it to the residual.

The exception, and what it is an exception to #

Five of the six accuracies behave the way the table above describes. The sixth does not, and it is the reason this sweep is worth a figure at every stop rather than one at the middle.

At 10⁻⁴ the ratio is 0.89 at ten truncations, 1.83 at thirty-four and 1.78 at ninety-eight. The first thing to notice is that it comes back down. An accumulated error does not do that: adding sixty-four more approximate operations to a factorisation that has already gone wrong does not make it slightly less wrong.

The second is where the movement is. Between the third row and the fourth the representation error moves from 1.195·10⁻⁵ to 1.207·10⁻⁵, which is one per cent, and the residual moves from 1.063·10⁻⁵ to 2.214·10⁻⁵, which is a factor of 2.08. It is not that the deeper tree stopped compressing; it is that the factorisation’s own answer took a step the representation’s did not.

And the third is that the excursion is not a property of the depth either. Swept at a quarter of a decade rather than a whole one, across all ten decades and all five trees — two hundred configurations — the ratio exceeds one at thirty-five of them, and the worst entries are these:

The second-largest excursion in the entire grid belongs to the tree that performs two truncations. The tree that performs ninety-eight is third. The tree that performs none is at 1.000 at every one of its forty tolerances, exactly, because with no truncation the factorisation and the representation are the same object and the ratio is an identity rather than a measurement. There is no ordering by count here at all, and a quantity with no ordering by count is not a function of the count.

Two staircases whose steps are in different places #

What the excursions are a function of is measurable, and it is a property of how a rank is chosen rather than of how many times one is chosen.

The rank kept by a truncation is the number of singular values above the tolerance, relative to the block’s largest. The top-level admissible block of this matrix — the coupling between the first half of the unknowns and the second — has a spectrum that falls geometrically: σ₂/σ₁ = 3.12·10⁻¹, σ₃/σ₁ = 7.58·10⁻², and thereafter a factor of between six and eight per column all the way down. Consecutive singular values are separated by most of a decade. So a tolerance moved by a quarter of a decade usually selects exactly the same rank, and occasionally selects one fewer, and the error the block commits is therefore a staircase in the tolerance rather than a line. That is rank as a decision applied to the format’s own knob, and it is the same mechanism that sets how many columns a digit is worth.

There are two staircases, because the tolerance is applied twice. Once to each block as the representation is assembled, and again to the same block after a Schur update has been added into it — and an updated block is not the block it was, so its spectrum has its gaps in different places. Swept at a twentieth of a decade at a leaf of 16, from 2.5·10⁻⁵ to 3.5·10⁻⁴, the representation’s error takes four steps and the factorisation’s residual takes eight, over the same window of tolerance. Each of the residual’s four extra risers sits one grid point below one of the representation’s, and the ratio exceeds one at exactly those four samples and nowhere else in the window: 1.29 at 3.16·10⁻⁵, 1.58 at 5.01·10⁻⁵, 1.83 at 10⁻⁴, 1.06 at 2.24·10⁻⁴.

So the excursion is a sliver. It is the band of tolerance in which the factorisation has already dropped a column and the representation has not yet, and the width of that band is set by how far apart two singular values of one block are. The comparison is between two quantities that both step, and it misreads by the width of one step wherever the steps fail to line up. Nothing in that description mentions how many truncations happened, which is why the fine grid finds it at two truncations and at ninety-eight alike, and why a decade grid finds only one instance of it: a comb sampled at ten times its own spacing shows one tooth.

What it is not is a defect in the residual. At 10⁻⁴ and a leaf of 16 the residual is 2.214·10⁻⁵, which is comfortably inside the accuracy that was asked for. The excursion lives entirely in the margin — the claim that the factorisation is no worse than the object it factorised — and that claim is the one that needs a caveat, not the claim that the tolerance is a knob. The same distinction is made whenever an accuracy is stated as a backward error rather than as a bound on the answer, and the reason a threshold on a short decaying sequence needs it is exactly the reason deciding that a zero has arrived is a decision and not a measurement.

The refusal #

The claim under test is the one the count invites: that the accuracy of a formatted factorisation is set by how many truncations it performs.

The assertion that a hundred truncations cost twice what none do is fed the two ends of this same sweep run at a second matrix size, where a shallow tree performs none and a deep one performs a hundred, and it fails. It fails in the direction nobody predicts, because the deep tree’s ratio is below the shallow tree’s rather than twice above it. That refusal is published rather than argued because the alternative is prose about what a computation would do, and the computation runs.

It is worth being exact about what survives it. The refusal does not establish that formatted arithmetic is free. It establishes that its cost is not indexed by the count — that the number of approximate operations, which is the one quantity a reader can see and the one the received warning is stated in, is the wrong variable. What the cost is indexed by is the tolerance, which was the parameter all along, and by where the tolerance happens to fall relative to a block’s own singular values, which is not a parameter at all.

What follows for anything built on the format #

The depth of the tree is not an accuracy decision. It sets the truncation count, the number of blocks and the size of the dense fringe, and it does not set the residual. That leaves it a trade between storage and locality — a 128 × 128 dense solve at a leaf is a well-behaved kernel and an 8 × 8 one is not — and it can be settled on the machine rather than against the problem, which is what the formatted copy of an ordinary Cholesky needed in order to be usable at all.

A margin claim needs a tolerance, not a count. A code asserting that its factorisation is no worse than its representation must say at which accuracy, because the sliver where that fails is real, is up to a factor of 3.7 wide, and appears at trees of every depth including one performing two truncations. A code asserting a residual against the tolerance it asked for needs none of this.

And the cost argument is unaffected. Whether the format is worth using is a question of where its multiplication count crosses a dense factorisation’s, and nothing measured here moves the accuracy at which that comparison is conducted. The reason the two arguments can be settled separately is the reason this sweep was worth running: the accuracy question turned out not to have the count in it.

What remains unmeasured is one order further out. Every ratio on these figures is checked against a dense reference, and an answer that is known has to be affordable for the comparison to mean anything. Ninety-eight is not nine hundred and eighty, and the honest form of the result is that it holds over the range where an exact reference exists — ten decades of tolerance, five depths, and a hundred-fold range of counts. Past that it is an extrapolation, and the ordering the fine grid failed to find is the reason to expect the extrapolation to hold rather than a proof of it.

One habit does transfer. Formatted addition is neither associative nor commutative, so the order the terms arrive in still changes the answer, and the scalar version of that question has a different answer from the one this format gives. The count does not decide the accuracy; the order still moves it, by about two per cent, which is the only thing on this page a reader should carry away as a knob rather than as a reassurance.