The correction lost to its own two-by-two solve

The circulant the problem did not contain took a band matrix that differs from a circulant only in its corners, solved it through the circulant by a fast transform — the closed-form spectrum the matrix that is one row established — and repaired the corners with a rank-two Sherman–Morrison–Woodbury correction. Its cost claim was exact. Its accuracy claim was measured and found wanting: on tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the corrected solve was wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination was right to 1.1·10⁻¹⁴. The essay explained the loss as two amplifications multiplied — the cancellation in the correction’s last line, and the condition number of the two-by-two capacitance matrix S — and it recorded, as a remark about its own method, that a code which solved S by elimination with pivoting instead of by Cramer’s rule “would change the constant of a tenth and not the slope, since S is two by two and the factorisation is the same arithmetic either way”.

Two near-zeros cost less than one built on that. A wrap whose samples land a conjugate pair on the symbol’s zeros left S perfectly conditioned; one that landed a single sample made S nearly singular and cost four orders of magnitude more in the answer, at the same condition number of the wrap. It ended by asking what happens when the correction has rank four and the symbol four zeros: whether the capacitance matrix is well conditioned exactly when the number of landed samples equals the correction’s rank.

Building the rank-four correction answered that question and, in passing, the first essay’s remark. It is not the same arithmetic.

The same correction, solved two ways #

A rank-four correction needs a four-by-four capacitance system, and nobody solves a four-by-four system by Cramer’s rule; the natural code is elimination with partial pivoting. The first single landing solved that way was harmless — its error was the cancellation’s, not four orders more. Setting the band’s outer coefficient to zero turns the rank-four correction back into the rank-two one on the same tridiagonal matrix, and the error stayed harmless. The only difference left between the two codes was how the small system was solved.

On the first essay’s own family the difference is not a constant. At σ = 10⁻⁴ the two solves give 3.1·10⁻¹³ and 4.2·10⁻¹⁴; at 10⁻⁶, 1.1·10⁻⁸ and 2.2·10⁻¹²; at 10⁻⁸, 1.2·10⁻⁴ and 2.9·10⁻¹⁰; at 10⁻¹⁰, 1.3 and 2.8·10⁻⁸. Cramer’s rule loses a hundred times the accuracy for every decade of σ; the pivoted solve loses ten. The pivoted curve lies on the cancellation times u at every σ — within a factor of two down to 10⁻⁹, and 8.5 at 10⁻¹⁰ — and that is the whole of its error. The slope is not the same slope.

So the first essay’s product law is a law about Cramer’s rule. The correction does lose accuracy against elimination, and the reason it gave for that is the right one: the intermediate $y = A^{-1}b$ is larger than the answer by the wrap’s near-singularity, and subtracting to get the answer loses the ratio in relative accuracy. At σ = 10⁻⁸ that is 1.7·10⁻¹⁰ of the answer, twenty thousand times elimination’s error. What is not real is the second factor. The capacitance matrix’s condition number, 6.2·10⁶ there, is not multiplied onto anything when the two-by-two system is solved stably.

Where Cramer’s rule loses it #

A rule that is correct and unusable measured Cramer’s rule on its own: on two-by-two systems whose rows are nearly parallel it returns an answer with a backward error of 458 units of roundoff where elimination returns 1.3. The capacitance matrix of a nearly singular wrap is such a system, and its entries are large.

Cramer’s rule divides by $\det S = s_{00}s_{11} - s_{01}s_{10}$. When S is nearly singular that difference is much smaller than either product, and each product carries a rounding error of u relative to itself, so the computed determinant is wrong by u times the ratio of product to difference. Elimination never forms the difference: it divides the second row by the first row’s pivot and subtracts, which is a backward-stable operation whatever the rows’ near-parallelism.

The ratio is the loss, and it is readable directly. On the Laplacian’s wrap and on the single landing it rises with κ(S) along a line a little under the diagonal — 2.3·10³ at κ(S) = 9.1·10³, up to 2.3·10⁸ at κ(S) = 9.1·10⁸ — so every digit of κ(S) is a digit Cramer’s rule throws away in the determinant, and it throws it away in both components of the solution at once. On the paired landing the ratio is 1.0 at every distance: the two products in the determinant are not close to each other, because a pair leaves S near the identity and $s_{01}s_{10}$ near zero. That is why the paired landing looked safe and the single did not. It was never the landing that was safe. It was the determinant.

The landings, again #

The second essay’s comparison is worth redrawing with both solves, because it was the comparison that made the conditioning of S look like the mechanism.

At 0.3 of a turn a single sample is landed on. Ten to the minus nine of a turn from the landing, κ(S) is 9.1·10⁸, Cramer’s rule returns an answer wrong by 4.2 — worse than no answer — and the pivoted solve returns one wrong by 5.0·10⁻⁸, against a cancellation times u of 2.9·10⁻⁹. At 10⁻⁵ of a turn the figures are 3.0·10⁻⁸ and 2.8·10⁻¹².

Turn the dial to 0, where a real wrap lands both zeros of the pair, and the two solves coincide at every distance — 9.8·10⁻⁸ at the nearest, against a cancellation times u of 2.7·10⁻⁸. The pair’s error and the single’s pivoted error differ by a factor of two at matched distances. The four orders the second essay measured between them are the difference between S’s determinant cancelling and not cancelling, and when S is solved without forming its determinant there is nothing between them to measure.

What survives of that essay is real and worth keeping. The twist decides which samples of the symbol the wrap takes, and so how nearly singular the wrap is; that sets the cancellation, which is the correction’s genuine loss, and reading the twist off the symbol’s zeros is the right way to keep it small. The claim that a single landing is uniquely expensive does not survive.

Refinement, and what it was paying for #

The first essay found that refinement against the band matrix repaired the corrected solve, pass by pass, and measured the passes it took. That measurement too was a measurement of Cramer’s rule.

With Cramer’s rule the error goes 5.1·10⁻⁵, 5.3·10⁻⁹, 4.2·10⁻¹², 1.9·10⁻¹⁴ — three passes to reach elimination’s accuracy, each one clearing about four digits. With pivoting it goes 7.8·10⁻¹¹ and then 6.5·10⁻¹⁵: one pass. That is what refinement should do for a solver whose error is a fixed relative loss — here the cancellation — against a residual computed accurately; each pass multiplies the error by that loss, and a loss of 10⁻¹⁰ is cleared in one. Under Cramer’s rule the loss per pass was the cancellation times the determinant’s cancellation, and three passes were the price of the second factor. The corrected solve with a stable two-by-two system and one refinement step is as accurate as elimination on the band matrix and keeps the transform’s cost.

The gap refinement can close measured the general version of this: a solver that is not backward stable, refined at the working precision against an accurately computed residual, is repaired — and how quickly depends on how large the solver’s own relative error is, which is exactly the quantity the two solves here differ in. Cramer’s rule made the corrected solve’s relative error the cancellation times the determinant’s cancellation, two factors each growing with the wrap’s near-singularity, and the refinement had to clear both; the pivoted solve leaves only the first, and one pass clears it. The refinement count the first essay reported is therefore a reading of the small system’s solver, not of the correction.

A correction of rank four #

The question the second essay asked can now be answered on its own terms. The pentadiagonal band with symbol $(d_1 - 2\cos\theta)(d_2 - 2\cos\theta)$ has four zeros, and its corners differ from the wrap’s in a two-by-two block at each end, so the correction back to the band is rank four. A twist lands the wrap’s samples on the zeros in any of six arrangements: none; one conjugate pair; both pairs; one sample; two samples on the same side of zero; and one sample beside the mirror image of the other zero.

The capacitance matrix is perfectly conditioned in exactly one arrangement: both pairs landed, four near-null samples for a correction of rank four, κ(S) = 1.00. With one pair landed — the arrangement that was perfect at rank two — κ(S) is 2.4·10⁷. With one sample landed it is 1.7·10⁸; with two samples on one side, 1.8·10⁷; with two crossed, 3.9·10⁷; with nothing landed, 15. So the second essay’s conjecture holds in its sharp form: the capacitance matrix is well conditioned when the number of near-null directions the wrap brings in equals the rank of the correction that has to remove them. At rank two a pair fills the rank; at rank four a pair leaves two columns of the correction with nothing to cancel, and S is as badly conditioned as it is for a single landing.

And it does not matter. Solved with pivoting, the rank-four correction’s error is 2.3, 3.5, 28.9, 3.5 and 4.4 times the cancellation times u across the five arrangements that land anything, and the arrangement with κ(S) = 1 is not the most accurate of them — one pair landed, at κ(S) = 2.4·10⁷, is. The single landing is the worst at 29 times, a factor of ten over the others for a condition number ten times higher, which is the only trace of κ(S) in the errors: nothing like its eight orders. The arrangement with nothing landed has an error of 1.7·10⁻¹⁴, eighty times a cancellation that is itself negligible there, so its error is the base solve’s rounding rather than anything the correction does.

The conjecture is true and it is bookkeeping. Whether the capacitance matrix is well conditioned says how the correction divides the work between the transform solve and the small system; it does not say what the answer costs, because a stably solved small system does not multiply its condition number onto the answer.

The same lesson, a fourth time #

The same failure has appeared before, three times, each time in a formula that is exact algebra and a bad computation.

A correction cheaper than the problem measured Sherman and Morrison’s formula — the rank-one case of the correction here — returning a forward error of 2.5·10⁻⁴ on a system whose updated matrix was the identity, because the formula passes through the inverse of the matrix before the update, and that matrix was nearly singular. The inverse that is never formed measured the general case: $x = A^{-1}b$ is how a solution is written and not how it is computed, because the route through an explicit inverse is not backward stable and the route through a factorisation is. The number that decides nothing measured the determinant itself as a quantity, and found it wrong on matrices of modest size and uninformative about conditioning on matrices where it was right.

The corrected circulant is all three at once. It is a low-rank update formula; the capacitance system inside it is small enough that writing its solution with an explicit inverse — which is what Cramer’s rule is, for a two-by-two — looks harmless; and the determinant it divides by is exactly the quantity that loses its digits. The difference from the three earlier cases is that here the cost of the bad route was not visible as a bad route. The two-by-two system is so small that “solve it by the formula” and “solve it properly” sound like the same instruction, the earlier essay said so in as many words, and the measurement that would have separated them was never made, because the loss it produced had an explanation ready: the correction was losing accuracy, and it was nearly singular, and the numbers fitted a product law.

The measurement that separates them costs one line: solve the small system with a row interchange and see whether anything changes. It changed the slope.

Why an ill-conditioned S costs nothing #

That last statement needs a reason, since a nearly singular system normally does amplify errors. The reason is where S’s size comes from. As the wrap nears singularity, $A^{-1}$ applied to anything has one enormous component — along the near-null vector of the sample that is nearly landed — and $S = I + V^{\mathsf H}A^{-1}U$ inherits that component as one large, nearly rank-one term. The right-hand side $r = V^{\mathsf H}A^{-1}b$ inherits the same component in the same proportion, because it is computed through the same $A^{-1}$. The small system’s near-singularity is along the direction in which S and r are large together, and a backward-stable solve of that system returns the w that makes the correction’s last line, $y - Zw$, cancel the large component of y against the large component of Zw. What is left is the answer, with the rounding of the cancellation and no more — which is what every measurement above shows.

Cramer’s rule breaks this by computing the determinant first. The determinant is small exactly because the large term is rank one, and computing it as a difference of two large products throws away the information that the large term was rank one. Every later step divides by that damaged number.

What this does not settle #

Every rank-two measurement is on the families the two earlier essays used — the tridiagonal Laplacian and the simple-zero symbols at n = 64 — with five seeded right-hand sides. The rank-four band is one symbol family, one size, one distance from landing; the rank-four errors are medians of five, and the factor-of-ten spread between arrangements is within what five draws can resolve only roughly.

The explanation of why an ill-conditioned S is harmless is an argument about where S’s large entries come from, checked only through its consequence — the error equalling the cancellation — and not by measuring the alignment of the rounding in S and r directly. A correction whose U and V did not see the near-null vector symmetrically might break it, and none is measured here.

The earlier essays’ figures still draw what they drew: the corrected solve with Cramer’s rule. Their numbers are right about that computation. What they attributed to the correction belongs to the rule.

Still open: the cancellation as the only cost, and bands with more zeros than the correction has columns #

Removing the cancellation. With the capacitance system solved stably, the corrected solve’s only loss is that the intermediate y is larger than the answer. A twist chosen to keep the wrap’s samples off the zeros keeps y small, and the earlier essays found where to put it; whether some twist makes y no larger than the answer for every symbol — so that the corrected solve is as accurate as elimination with no refinement at all — is the question the cost claim now rests on.

More near-null directions than columns. At rank four the symbol has at most four zeros, so the landings can never outnumber the correction’s columns. A banded matrix whose symbol has a zero of high order — the square of the Laplacian, whose symbol vanishes to fourth order at the origin — brings several nearly null samples in at once from a single zero, and a correction of fixed rank then has fewer columns than near-null directions. Whether a stable small solve is still enough there, or whether the cancellation itself grows faster than the wrap’s condition number, is the measurement the rank-four band cannot make.