The knob that moved two things

One sentence in this collection can be acted on before anything runs: decide how many digits the answer needs, divide by the condition number, and compress to that. It was earned by the essay that showed a compression tolerance is a backward error — the perturbation is written down in advance and applied on purpose, so both factors of the amplifier identity are known before the solve starts, and the product is a prediction rather than a diagnosis.

That is the only sentence of its kind in this collection. Everywhere else a backward error is something an algorithm produced and somebody then measured, so the identity explains an answer that has already arrived and cannot be used to commission one. Here it runs forwards.

A sentence a code acts on has to be priced. Pricing it means asking what happens to each of the two factors when something else in the set-up moves, because the rule reads as though they were independent inputs a caller supplies. Two things can move here before a tolerance is typed. The problem can get bigger. And the partition the representation is built on can be rebuilt with larger or smaller dense blocks at the bottom of its recursion — a choice about where the subdivision stops, made once, and not a statement about accuracy at all.

Neither is a tolerance. Both were expected to leave the rule alone, and they do not, and they fail in opposite directions. The leaf moves neither factor of the identity and moves the answer by nearly a factor of three. The shift that is the only route this representation has to a larger condition number moves both factors at once, and moves the second one in the direction nobody budgets for.

The slack in the bound does not grow with the problem #

The prediction is an upper bound and an upper bound is only useful if its slack is bounded too. A code told to divide by κ is being told to buy digits it may not need, and how many it over-buys is the gap between the two lines above.

At 64 unknowns the six measured forward errors are 0.0016, 1.8·10⁻⁵, 9.5·10⁻⁸, 1.2·10⁻⁹, 7.5·10⁻¹² and 2.5·10⁻¹³ against predictions of 0.019, 2.3·10⁻⁴, 2·10⁻⁶, 10·10⁻⁹, 5.5·10⁻¹¹ and 1.9·10⁻¹². Averaged over the six, the bound over-predicts by a factor of 12.

The first question a single-size measurement cannot answer is whether that factor is a property of the identity or of the matrix it was read off. Three sizes settle it. κ climbs from 17.43 to 20.88 to 24.39 — a rise of 40 per cent across a four-fold increase in the number of unknowns, which is what a well-behaved kernel does and is why this operator is a fair place to ask the question at all. The mean over-prediction across the same three sizes runs 12, 16, 14. It rises and then falls, it stays inside a factor of one and a half, and it does not track the size.

So the slack belongs to the right-hand side rather than to the problem’s growth. That is the useful direction: a bound whose looseness grew with n would be a bound that stopped licensing the rule somewhere, and a caller would have to know where. This one does not, over the range that can be measured against a dense reference.

The range that claim is made over is worth naming, because it is small and it is small for a reason. The prediction is checked against a forward error, and a forward error needs the true answer, so every point on these figures is a problem whose dense solve is affordable. Sixty-four to two hundred and fifty-six unknowns is where that holds, and it is three sizes rather than a curve. What it supports is the absence of a trend across a four-fold range, which is a weaker claim than a growth rate and is the one being made.

The slopes are worth reading beside those numbers, because they are the check that the two lines are parallel rather than merely both descending. Fitted across ten decades they are 0.970, 0.971 and 0.981. A slope below one would mean the measured error falling more slowly than the prediction, which is the shape a bound loses its grip in, and three fits within three per cent of one over ten decades are not that shape.

A knob the rule cannot see #

The partition is built by bisecting the points until each piece is small enough, and small enough is a number. Set it to eight and the recursion goes one level deeper than at sixteen; set it to thirty-two and it stops one level earlier. The blocks that remain are tested for admissibility and compressed exactly as before.

Nothing in that decision is about accuracy, and the two factors of the rule agree. κ is a property of the matrix, and the matrix is the same one however it is cut up: at every size measured, all three leaves give the identical condition number to four digits. The chosen backward error does not move either. At 128 unknowns and a tolerance of 10⁻⁸ the assembled representation’s error is 1.415·10⁻⁹, 1.413·10⁻⁹ and 1.413·10⁻⁹ across the three leaves — the same number to three digits, three times.

The ranks do not move at all. At 128 unknowns the maximum rank the partition asks for runs 3, 6, 8, 10, 12, 14 across the six tolerances, and it runs 3, 6, 8, 10, 12, 14 at each of the three leaves. The rank is a number of digits and the leaf does not change how many digits a block needs, which is exactly what the essay on where the ranks come from would predict.

Everything the rule reads is therefore invariant under the leaf. What is not invariant is the answer. At the same tolerance of 10⁻⁸ the forward error is 3.83·10⁻⁹ at leaf eight against 1.55·10⁻⁹ at sixteen and 1.55·10⁻⁹ at thirty-two: the deeper partition returns an answer two and a half times less accurate from a representation whose error is the same to three digits.

It is worse at every tolerance, not at one. The six forward errors at leaf eight are 4.95·10⁻³, 2.07·10⁻⁵, 2.97·10⁻⁷, 3.83·10⁻⁹, 2.29·10⁻¹¹ and 3.05·10⁻¹³ against 1.72·10⁻³, 1.86·10⁻⁵, 2.08·10⁻⁷, 1.55·10⁻⁹, 1.72·10⁻¹¹ and 3.05·10⁻¹³ at leaf sixteen — a factor between 1.0 and 2.9, always in the same direction.

The leaf does change something a caller pays for, and the sign of the change depends on the tolerance, which is the reason it is a real knob rather than a dead one. At 256 unknowns the numbers stored run 9,728, 15,872, 19,968, 25,088, 29,184 and 32,768 across the six tolerances at leaf eight, and 13,312, 17,408, 20,480, 24,064, 27,136 and 29,696 at leaf thirty-two. At the loosest tolerance the deeper partition is 27 per cent cheaper, because a shallow tree keeps large dense blocks that a rank of four would have summarised; at the tightest it is 10 per cent dearer, because the same rank is now being stored on many more blocks. The two curves cross between 10⁻⁶ and 10⁻⁸. So the leaf is a storage decision whose right answer depends on the accuracy wanted, which is a familiar shape here and is not what this section is about — what this section is about is that it is also an accuracy decision, and that one is invisible.

The tightest bound sits on the worst answer #

Read those three figures as a sequence and something uncomfortable falls out. The gap between the prediction and the measurement narrows as the leaf shrinks — 18, 16, 10 at 128 unknowns — and a narrowing gap is what a sharper bound looks like. It is not what happened. The prediction did not move, because neither of its factors moved. The measurement rose to meet it.

A tighter bound here is a worse answer. Anyone tuning the partition to make the amplifier’s prediction sharp would be tuning towards a solve that loses two and a half times more accuracy for the same typed tolerance, and the instrument would report success.

The nine combinations, at the tolerance the badge on each figure reads:

The condition-number column is constant down each block of three and the rank column is too. The forward-error column is not, and it separates leaf eight from the other two at every size by a factor between 2.3 and 2.9. The one place the representation error moves at all is the smallest matrix, where leaf eight sits 13 per cent above the other two — at 128 and 256 unknowns it agrees to three digits and there is nothing to attribute the accuracy difference to.

What the difference is attributable to is not settled here, and it should not be asserted from the table. The bound between the two quantities is a matrix norm applied to one particular right-hand side, and the gap between a residual and an error is exactly that gap. A deeper partition builds the same perturbation out of more, smaller truncations, and how much of it a given vector sees depends on how the pieces align with that vector rather than on how large they are. The measurement that would test it is the residual rather than the forward error, and the residual moves the same way: 2.42·10⁻¹⁰ at leaf eight against 1.42·10⁻¹⁰ at sixteen, at 128 unknowns and a tolerance of 10⁻⁸. So the loss happens before the condition number is applied, which rules out the other candidate.

The practical form is short. The leaf is a cost knob and not an accuracy knob — it is the one the crossover essay prices in multiplications — and it changes the accuracy anyway, without changing anything the rule inspects. A code that reads the rule as a contract has to fix the partition before the contract means anything.

The other knob moves both factors at once #

The second half of the rule is the condition number, and the interesting question about a rule that divides by κ is what happens when κ is large. This representation has exactly one way of arranging that: the kernel’s entries are f(|x − y| + δ), and δ can be enlarged. It is the sweep the cost essay runs, and it moves κ over two and a half decades.

δ is not a conditioning parameter. It does not touch the geometry the partition is built from — every distance between every pair of clusters is exactly where it was, every admissibility test returns the same verdict, and the tree is the same tree. That is why it was chosen: it looked like a way to move one factor of the identity and leave the machinery alone, in the way the barrier field’s diagonal moves a spectrum without touching a structure.

It does not leave the machinery alone. δ sits inside the kernel’s own argument, so enlarging it moves every evaluation away from the singularity and makes the kernel smoother — and a smoother kernel is a more compressible one. At 64 unknowns the maximum rank the partition asks for at a fixed tolerance of 10⁻⁸ falls 9, 8, 6, 4 across the four shifts, while κ climbs 17.4, 134.5, 1,046 and 6,340. At 128 unknowns it falls 10, 9, 7, 5 against κ climbing 21, 175, 1527 and 1.1·10⁴.

The ranks halve while the condition number rises by more than two and a half decades. The harder problem is the cheaper one to compress.

What the rule actually costs when κ is raised #

That coupling is not a curiosity about ranks. It changes the arithmetic of the rule, and by enough to reverse its sign.

Take the rule at its word. Ask for a forward error of 10⁻⁶, compress at 10⁻⁶ divided by the condition number of the problem in hand, and count what the representation stores. The naive expectation is plain: κ rises by a factor of 364 across the sweep, so the tolerance must tighten by 364, and a tighter tolerance costs rank. At 64 unknowns, against a dense matrix of 4,096 numbers:

The storage falls by 26 per cent while the tolerance tightens by a factor of 364. The last column is the counterfactual: the same four tolerances applied to the original shift, where the ranks are what they were, and it rises by 17 per cent as expected. The two columns end 59 per cent apart. At 128 unknowns the same experiment reads 8,448, 8,448, 7,424 and 5,888 numbers against a counterfactual of 8,448, 9,216, 9,472 and 10,240, which is 74 per cent apart at the hard end.

The counterfactual column is a decomposition rather than an alternative anybody could have chosen. No knob on this representation produces it: there is no way to raise κ and hold the kernel’s decay fixed, which is precisely the finding. It is there to answer the question the actual column raises — how much of the fall is the tolerance being tightened and how much is the ranks being handed back — and the answer is that the second effect is larger than the first and pointing the other way, by 17 per cent against 26.

So the account “a harder problem forces a tighter tolerance and a tighter tolerance costs storage” is not merely quantitatively off. It is wrong in sign, over the only range in which this representation can be made hard. The forward errors obtained sit at 2.02·10⁻⁸, 1.25·10⁻⁸, 3.64·10⁻⁹ and 8.88·10⁻⁹ — inside the 10⁻⁶ that was asked for at every point, by roughly the over-prediction the first half of this essay measured, so the rule delivered what it promised while being paid the wrong price for it.

The reason the two columns diverge is that the rule’s two factors are not two knobs. There is one knob here, and it turns both.

The assertion that could not see it #

The collection’s own check on that sweep passed the whole time, and it is worth saying exactly why, because it is the failure mode this site’s habit is built against.

The check bounds the spread of the ranks at a fixed tolerance: their maximum minus their minimum must not exceed six. Measured, the ranks run 10, 9, 7, 5, so the spread is five and the check passes with room. A spread of five is also what a rank wandering up and down by a couple would give, and it is what a rank falling monotonically by half gives. The assertion cannot tell those apart, and the sentence attached to it read the pass as evidence that δ is not a geometric quantity.

A bound on a spread cannot see a trend. The four ranks are monotone decreasing at both sizes measured — 9, 8, 6, 4 and 10, 9, 7, 5, eight numbers with no exception — and monotonicity is a one-line check that the spread bound was standing in for. That the two look alike is the whole danger: a passing assertion had been read as licensing a claim it was never tested against, and the claim then propagated into the sentence that says the geometry did not move.

The general form is one this collection meets often enough to name. An assertion is evidence for exactly the statement it would fail on, and a statement that sounds like it is not it. Here the statement it would fail on is the ranks stay within six of each other, which is true; the statement it was carrying is the ranks do not respond to δ, which is false.

What follows for a code that uses the rule #

The rule survives all of this. What changes is what has to be fixed before it is quoted.

Fix the partition first. The rule’s two factors are blind to the leaf, and the leaf moves the delivered accuracy by up to a factor of 2.9 at a constant rank and a constant representation error. A tolerance chosen by the rule is a promise about a particular partition, and moving the partition afterwards breaks it silently, because nothing the rule reads has changed.

Do not read the slack as quality. The over-prediction factor runs from 7 to 18 across the grid, and the smallest values sit on the least accurate solves. An implementation tuned to make the bound sharp is an implementation tuned to lose digits.

Expect the price of accuracy to fall as the problem hardens, on a kernel with this structure. The rule asks for a tighter tolerance and the geometry supplies part of it free. That is a favourable coupling, and it is favourable only because it happens to run this way — a shift applied to the spectrum rather than to the kernel’s argument would tighten the tolerance and leave the ranks where they were, and then the naive account would be right.

Quote κ with the matrix it belongs to. Here κ is a property of the operator and not of the representation, which is what makes the rule usable at all — but a condition number quoted alone is not a measurement, and κ read as a choice of units is the reading that keeps the rule honest when the same matrix is scaled.

And none of this survives contact with an outer iteration, in the good direction. A hierarchical representation used as a preconditioner is repaired by the loop around it, because the residual the method stops on is computed from the true matrix at every step. The rule is for the case where the compressed solve is the answer, which is the exact answer to a nearby problem and nothing more — and the essay that moves a condition number on purpose is the other end of the same idea, where the problem is altered to make the amplifier smaller rather than measured to divide by it.

The refusal #

The claim under test is the one every tolerance in every manual invites: that a compression tolerance is the error of the matrix it produces.

It is not, and the direction is the flattering one, which is why it survives. The measurement is made on the unshifted kernel matrix this field’s storage measurements use rather than on the shifted one solved above, and in the Frobenius norm rather than the two-norm the identity is stated in, which is why its numbers do not line up with the tables here — the claim being refused is about a tolerance and a representation, and neither the kernel nor the norm changes it. At 128 unknowns, compressed at 10⁻⁸, the assembled error is 2.75·10⁻¹⁰ — thirty-six times smaller than the number that was typed. Across six tolerances the ratio of the two runs 0.053, 0.040, 0.031, 0.028, 0.032 and 0.044, so the representation is consistently between nineteen and thirty-six times better than asked and the factor is not a constant either.

The assertion that the assembled error is the tolerance, to within a factor of a half, is fed that number and it fails. That refusal settles the first link of the chain this essay follows: from a tolerance a caller types, to the perturbation actually built, to the residual that perturbation produces on one right-hand side, to the digits in the answer. Each link has a factor in it, the factors are computed from unrelated things, and a code that assumes any of them is one has guessed.