A threshold that holds the growth still

A margin the factorisation records found that partial pivoting could keep the second-largest candidate its scan finds at every step, and that the gap between the two largest, taken over the steps before half the growth arrives, says how much noise the growth can take. Divided by the growth reached, it predicts the dense noise that halves the growth; undivided, it predicts the noise that keeps the matrix’s zeros, at a third to a half of the margin. And it gave a code a reading of its growth factor: “Large growth, r½ zero or at rounding. The growth rests on exact ties. It is an accident of how ties are broken, a perturbation of the size of the rounding removes it.”

It left the version a sparse solver could run as the open question. A sparse code does not choose the largest candidate. A threshold between fill and growth measured how it chooses: among the candidates at least τ times the largest in magnitude, it takes the one whose row has the fewest nonzeros, trading some stability for less fill. “Its margin is not a gap between the two largest but the gap between the chosen candidate and the threshold, and whether the same ratio predicts what noise does to a threshold-pivoted growth is the version of this check a sparse solver could actually run.”

The ratio does not; the margin does, undivided. And the reading of a tie-based growth reverses: under a threshold, it is the hardest growth to remove.

The same growth at every threshold #

The matrices are the two these essays have worked with. The multiple-shooting matrix of a boundary-value problem, at intervals of 6 to 15 and steps of 0.15 to 0.3, grows under partial pivoting by $e^{5T/6}/2$ — 75 at an interval of 6, 1.3·10⁵ at 15 — because at every continuity row the elimination prefers a −1 to a transfer-matrix entry that is smaller than one by 5.6·10⁻³. Wilkinson’s matrix grows by $2^{n-1}$ because every candidate in every column is ±1 and partial pivoting, meeting ties, keeps the rows in order.

Factorised with a threshold, both do exactly the same. At τ = 0.99, 0.9, 0.5 and 0.1, every shooting matrix reaches precisely its partial-pivoting growth, and Wilkinson’s matrix of order 24 reaches 2²³ = 8,388,608 at every threshold. The fill is the same too, 158 entries on the shooting matrix over 12, because the sparsest qualifying row turns out, on both matrices, to be the row partial pivoting chose.

So on these matrices a threshold buys nothing in fill and costs nothing in growth. What it changes is why each choice was made, and that is what decides what noise can do to the growth.

Stored noise, and the growth it cannot reach #

A sparse code perturbs values and never its pattern: rounding in the entries, an error in a coefficient, a slightly different transfer matrix. So the noise here goes into the stored entries only, and the zeros stay zero. Under partial pivoting that noise is not amplified by the elimination — noise the growth amplifies found that only noise sitting in the zeros is — and it halves the shooting matrix’s growth when it is comparable with the margin itself.

At τ = 1, which is partial pivoting, the shooting matrix keeps its whole growth up to noise of 10⁻³ and loses it by 3.2·10⁻³, against its margin of 5.6·10⁻³. Wilkinson’s loses its growth at the first noise drawn: the ties are broken by the noise and the rows are reordered, as the preceding essays found for dense noise.

Turn the dial. At τ = 0.9 the shooting matrix keeps its growth to 3.2·10⁻² and loses it at 5.6·10⁻²; at 0.5, to 0.18 and loses it at 0.32; at 0.1, it keeps it to 0.32 and loses it at 0.56 — noise more than half the size of the entries. Wilkinson’s matrix, which at τ = 1 had no robustness at all, keeps its 2²³ at τ = 0.5 and 0.1 until the noise reaches 0.18. The growth has not changed. The noise it takes to remove it has risen by a factor of three hundred on the shooting matrix and by fifteen orders of magnitude on Wilkinson’s.

Why: a choice made by counting #

Under partial pivoting the choice at each step is a comparison of magnitudes, and noise reverses it by reversing the comparison. Under a threshold, the magnitudes decide only which candidates qualify. Among those, the choice is made by counting the nonzeros in each candidate’s row, and counts are structure. Noise on stored values leaves every count exactly where it was.

So a threshold choice can change in only two ways. The chosen candidate can fall below the line τ times the column’s largest, or a candidate in a row at least as sparse can rise above it. Both require noise comparable with a candidate’s distance from the line. On the shooting matrix, the chosen −1 sits at the top of its column, 1 − τ above the line; the transfer-matrix entry beside it, at 0.994, sits just below it, but its row is denser and crossing the line would not make it the choice. On Wilkinson’s matrix every candidate is ±1, so every candidate sits at the top of the column, 1 − τ above the line, and the ties among them are broken by counts, which noise does not touch.

That is what inverts the reading of a tie. A tie between magnitudes is the most fragile thing a comparison can rest on and the most robust thing a count can rest on, because a count does not look at the magnitudes that tie.

Against the fragility the earlier essays measured #

The two readings the earlier essays built their account of fragility on were both partial-pivoting readings, and it is worth setting them beside the new ones. A worst case is as fragile as its margin found Wilkinson’s growth of 5.5·10¹¹ at order 40 taken to exactly 2 by dense noise of 10⁻¹⁴, and read that as the measure of how little the worst case rests on: exact ties, which any noise breaks. The bound that is never attained had already said why such a worst case does not trouble anyone in practice, since random matrices grow by about three and the constructed one needs its ties.

Under a threshold the ties are not broken by noise, because the threshold never compares the tied magnitudes with each other; it only asks whether each is within τ of the largest, and all of them are. The construction that was the standard example of an accident becomes, under the pivot rule sparse direct solvers commonly use, a growth that survives perturbations of a fifth of the entries. Nobody factorises Wilkinson’s matrix on purpose, and the point is not that matrix. It is that the reassurance “large growth needs a delicate construction, and delicate constructions do not survive real data” is a statement about partial pivoting’s comparisons.

The shooting matrix is the practical case, and the growth a boundary-value problem supplies is where it came from: multiple shooting, a standard method, producing a growth of 1.1·10⁴ on a matrix whose condition number never exceeds 8.3. Under partial pivoting that growth already survived every stored perturbation below its margin of 5.6·10⁻³. Under a threshold of 0.1 it survives perturbations a hundred times larger than that margin. A sparse solver applied to a multiple-shooting system — which is sparse, block bidiagonal apart from its boundary rows — meets this growth and cannot perturb its way out of it.

There is a sense in which the threshold does what it was designed to do and more. Structure and stability stop being separable measured a sparse choice that accepted a pivot of 10⁻¹² because its row was the sparsest, and got an answer wrong in the fifth digit; a threshold exists to stop that. Here it has nothing to stop, because every qualifying pivot is of order one, and what it contributes is only its tie-break — which happens to be the one property of the choice that noise cannot touch.

The margin a threshold code can record #

The quantity to record follows from the two ways a choice can change. At each step, take the chosen candidate’s relative height above the threshold line, and the relative distance below the line of any candidate in a row at least as sparse; the smallest of those is the step’s margin. At τ = 1 the chosen candidate is the line, and the margin is the gap to the second largest — the preceding essay’s quantity, recovered as a special case. As before, only steps before half the growth has arrived can take half of it away, so the recorded number is the smallest margin among them.

The trace shows the two margins as the factorisation records them. Under partial pivoting the margin at every continuity step is 5.6·10⁻³, the gap between the −1 and the transfer entry. At τ = 0.5 it alternates between 0.5, the −1’s height above the line, and 0.21, the distance below the line of a smaller entry in a sparser row, and its smallest value before half the growth is 0.21. The growth climbs identically underneath both.

Over the thirty-nine cases with a nonzero margin — seven shooting matrices and Wilkinson’s at four or five thresholds each — the noise that halves the growth is between 0.20 and 15 times the recorded margin, and between 0.20 and 1.6 times it on thirty-six of them. The three outside are all at τ = 0.99 with steps of 0.25 and shorter, where the transfer entry sits just above the line, 7·10⁻⁴ to 4·10⁻³ from it; noise that pushes it below the line changes which row is chosen but not the growth, since the row chosen instead leads down the same chain. The record errs on the safe side there, and it never errs the other way: the growth has never been halved by noise smaller than a fifth of the recorded margin.

No division by the growth #

The number is compared with the noise directly. The preceding essay divided its margin by the growth to predict dense noise, because noise that sits in the zeros is multiplied by the growth already made before it reaches a comparison. Stored noise is not, and on these matrices the noise that halves a threshold-pivoted growth does not depend on how large the growth is: at τ = 0.9 it is 5.6·10⁻² on every shooting matrix, whose growth runs from 75 to 1.3·10⁵.

Divided by the growth, the recorded margin would have predicted noise of 7.5·10⁻⁷ for the shooting matrix over 15 at τ = 0.9, and the measured noise is 5.6·10⁻², seventy-five thousand times more. The ratio the open question proposed is the right quantity for a perturbation the elimination amplifies, and a sparse code’s perturbations are not of that kind.

Set beside that figure, the two predictions are the same recording read for two different perturbations. The dense-noise prediction runs from 10⁻⁸ to 10⁻⁴ across the seven matrices because it is divided by growths that span three and a half decades. The stored-noise predictions sit in a narrow band at each threshold because nothing divides them. A dense factorisation that meets noise in its zeros — rounding in a computed matrix whose zeros are not exact — needs the first; a sparse code, whose zeros are structural and stay zero, needs the second. What a code records is the same margin either way.

What the growth now is #

A threshold therefore changes what a growth factor means. Under partial pivoting, the preceding essays built a reading on fragility: a growth that noise at rounding removes is an accident, a growth that survives noise at the margin is a property of the matrix, and a code could tell the two apart from one recorded number. Under a threshold, every growth measured here survives stored noise of at least a few per cent below τ = 0.9 and of order the entries themselves at 0.1. None of it is an accident the data can undo. If it is to be removed, the pivot rule has to change, not the data.

That is a real consideration for the direct solvers that use thresholds, because their growth is exactly as large as partial pivoting’s on these matrices and a good deal harder to shake. The ordinary safeguard in such a code is to check the backward error and refine — which a threshold between fill and growth found necessary on its own matrices — or to raise the threshold towards one. On the shooting matrix raising it does not help: the growth is 1.1·10⁴ at τ = 1 as well. Only a rule that looks along a row as well as down a column, as a pivot that searches one row and one column measured, removes it.

And a code cannot remove Wilkinson’s growth by the random tie-break the preceding essay suggested, since a threshold code’s ties are broken by counts before magnitudes are compared. It would have to randomise among rows of equal count, which is a change to the ordering a sparse code usually takes some trouble over.

What a threshold code should record #

The recording costs nothing a threshold factorisation does not already compute. It scans each column for its largest candidate to place the line, and it scans the qualifying candidates’ row counts to choose among them. Keeping the chosen candidate’s height above the line, and the smallest distance below the line among rows at least as sparse, is two comparisons per candidate on work already done. The minimum over the steps before half the growth is a running minimum and a second pass over a list the factorisation has anyway.

Read beside the growth factor, the number says how much the stored data could change before the growth changed. On the shooting matrix at τ = 0.1 it says 0.9 — no plausible perturbation — and on Wilkinson’s at τ = 1 it says zero. That is the same kind of reading the preceding essay offered, with the axis flipped: it describes how firmly the growth is held, not whether it is large.

What this does not settle #

Two matrix families, both with a single chain of growth, and noise that is Gaussian on every stored entry. A matrix whose growth comes from several interleaved chains, sharing rows, could have a choice decided by a count that one chain’s pivot changes for another; whether the recorded margin still bounds the noise there is not measured.

Row counts only, as Markowitz-style column counts are held fixed here. A code that permutes columns as well chooses by the product of row and column counts, and the argument that counts are immune to value noise holds for both; whether the choice lands on the same growing chain is a question about the pattern, not measured.

The noise grid is a quarter decade, so the ratios between recorded margin and measured noise are known to within a factor of 1.8 at each point.

Still open: several chains, and a threshold that notices #

Several growing modes. A boundary-value problem with several growing modes gives a transfer matrix with several entries near one and several chains sharing columns. Under partial pivoting noise amplified along one chain can land in another’s comparisons; under a threshold, the question becomes whether one chain’s choice changes a row count that another chain’s choice depends on, which is the only route left by which value noise could reach a count.

A threshold that raises itself. A factorisation that recorded large growth on a step could raise τ for the steps that follow, or switch to a rook search there, and pay for the stricter choice only where growth is being made. Whether that removes the shooting matrix’s growth — whose choice is the same at τ = 1 — or only moves where it happens, is the measurement that would turn the record into a repair.