A margin the factorisation records

A worst case is as fragile as its margin ended by proposing a check a code could run on every factorisation. Partial pivoting finds the largest candidate in each column, and in doing so it has found the second largest; their relative gap is that step’s margin, and a factorisation that kept the smallest margin beside the growth factor would know whether its growth rested on near-ties. It asked for the pair of numbers to be measured over random, constructed and practical matrices, to see whether it separates a growth that noise removes from one it does not.

Noise the growth amplifies then changed what that check has to look at. The noise that removes the shooting matrix’s growth is not the noise itself but the noise multiplied by the growth already accumulated: a comparison flips when σ times the growth reached there is a fixed fraction — 0.2 to 0.43 at the steps measured — of its margin. So the margin alone is not the quantity. The margin at a step, divided by the growth at that step, is.

This essay records that ratio during the factorisation and asks whether it predicts what noise does.

What is recorded #

At step k partial pivoting scans the candidates in column k. The scan keeps the largest in absolute value, and one more comparison per candidate keeps the second largest. The step’s margin is the gap between the two divided by the largest — the smallest relative change in the candidates that could reverse the choice. The factorisation already tracks the largest entry it has produced, so the growth so far, $G_k$, is free too.

The amplification law says a reversal at step k needs noise of about $m_k$/Gₖ, times a constant. A reversal removes the growth that was still to come, not the growth already made, so a reversal that halves the final growth must happen at a step where no more than half of it has arrived. The recorded quantity is therefore

and the prediction is that dense Gaussian noise of standard deviation about r½ halves the growth. It costs one comparison per candidate per step — about $n^2$/2 comparisons in a factorisation of $n^3$/3 multiply-adds, a share of 3/(2n) of the work, which is 1.8 per cent at n = 82.

Measured on seven shooting matrices #

The test matrices are multiple-shooting matrices for the same boundary-value problem over intervals of 6, 9, 12 and 15 at a step of 0.3, and over 12 at steps of 0.25 and 0.2 and over 9 at 0.15 — growth factors from 75 to 1.34·10⁵, sizes from 42 to 122. For each, r½ is read off one factorisation, and the noise that halves the growth is found by sweeping dense Gaussian noise upward from 10⁻¹⁶ in half decades until the median growth over fifteen draws is at most half the noise-free growth.

The measured noise spans three and a half decades, from 10⁻⁷ to 3.2·10⁻⁴, and the ratio of measured to recorded stays between 0.92 and 2.39. The measured column is on a half-decade grid, so each entry could be up to a factor of 3.2 above the true halving point, and the agreement is within that resolution everywhere. A number read off one factorisation, with no noise drawn at all, places the fragility of each matrix to within a factor of two or so.

Why the minimum has to be restricted #

The restriction to steps before half the growth is not a refinement; without it the prediction is wrong by two orders of magnitude.

The trace shows the structure the table rests on. The shooting matrix’s recorded margin is 5.64·10⁻³ at 80 of its 82 steps — the same comparison, $E_{11}$ against −1, made at every continuity step — while the growth so far doubles about every six steps, from 1 to 1.1·10⁴. The ratio of the two falls steadily. Half the growth has arrived by step 77, and the last step before it at which the ratio is smallest is step 75, where the growth is 5,200 and the ratio 1.08·10⁻⁶. That is r½.

The last two steps are different. Step 81 is one of the final comparisons, after the chain has ended, its two candidates are within 9.08·10⁻⁵ of each other, and the growth there is already the full 1.1·10⁴: the ratio is 8.2·10⁻⁹, the smallest anywhere. Read as a prediction it says noise of 10⁻⁸ halves the growth, and noise of 10⁻⁸ does nothing measurable to it. A reversal at step 81 changes how the last pivot is chosen after all the growth has been made, and the growth factor is the largest entry produced at any step, which that choice cannot reach back and remove.

So a naive recording — the smallest margin, or the smallest margin over growth, over the whole factorisation — is set by whatever comparisons happen at the end, where margins are often small for reasons that have nothing to do with the growth. On this matrix it under-predicts the noise by a factor of 120.

Over an interval of 15 the pattern repeats a decade further out. The growth reaches 1.34·10⁵; half of it has arrived by step 97; r½ is 8.9·10⁻⁸ at step 95, and noise of 10⁻⁷ halves the growth. The corner’s margin is smaller still, 7.45·10⁻⁶, and the unrestricted ratio is 5.6·10⁻¹¹ — eighteen hundred times below the measured noise.

The same record, read for noise that keeps the zeros #

The amplification that makes r½ the right quantity for dense noise is absent for noise that stays out of the zeros, and noise the growth amplifies found that such noise leaves the shooting matrix’s growth untouched until it is comparable with the margin itself. So the same recording supports a second prediction with the division by the growth taken out: noise on the nonzero entries halves the growth at a fixed share of m½, the smallest margin recorded before half the growth arrived.

Swept in quarter decades, the zero-keeping noise that halves the growth is 3.2·10⁻³ over intervals of 6, 9 and 15 at a step of 0.3 and 1.8·10⁻³ over 12, against a recorded margin of 5.64·10⁻³ at all four — a share of 0.56, 0.56, 0.56 and 0.32. At steps of 0.25, 0.2 and 0.15, whose margins are 1.07·10⁻², 1.34·10⁻² and 1.37·10⁻², it is 5.6·10⁻³ each time, a share of 0.53, 0.42 and 0.41. The growth across those seven matrices changes by a factor of 1,784 and the share stays between 0.32 and 0.56.

So one factorisation’s record answers two different questions with two different readings. Divided by the growth, the margin says how much noise that the elimination will amplify it can take. Undivided, it says how much noise it can take that the elimination cannot amplify — rounding in the entries, an error in the coefficients, anything that leaves the matrix’s zeros where they were. For a shooting matrix over 15 those two numbers are 8.9·10⁻⁸ and 3.2·10⁻³, thirty-six thousand times apart, and a code that knows which kind of perturbation its data carries knows which one to read.

The shortest interval is the case where the two readings are nearest. Over 6, the growth is only 75, half of it has arrived by step 37 of 42, r½ is 1.6·10⁻⁴ and dense noise of 3.2·10⁻⁴ halves the growth; the recorded margin is the same 5.64·10⁻³ and zero-keeping noise of 3.2·10⁻³ halves it. A factor of ten separates the two readings here, where over 15 it is thirty-six thousand, because the division by the growth is a division by 75 instead of by 1.3·10⁵.

Wilkinson’s matrix records exactly zero #

At Wilkinson’s matrix the recorded margin is 0 at the first step: every candidate in the column is exactly ±1, the largest and second largest are equal, and the gap is zero in floating point, not merely small. So r½ = 0, and the prediction is that noise of any size removes the growth.

The noise sweep confirms it at the resolution the sweep has: at both sizes, 24 and 40, the median growth is already at most half at the first noise level on the grid, 10⁻¹⁶. The recorded quantity has distinguished the two kinds of worst case without being told which is which — a tie records zero, a margin records a number, and the number is the noise it can absorb.

And what random matrices record #

The check is only useful if a matrix nobody has looked at records something interpretable, and the matrices a code mostly sees are not shooting matrices or constructions.

Forty random Gaussian 40 × 40 matrices grow by 2.19 to 4.81 and record r½ between 2.5·10⁻⁴ and 0.17. The seven shooting matrices grow by 75 to 1.34·10⁵ and record 8.9·10⁻⁸ to 1.6·10⁻⁴. Wilkinson’s grow by 8.4·10⁶ and 5.5·10¹¹ and record zero.

r½ alone does not separate the random matrices from the shooting matrices. The shortest shooting interval records 1.6·10⁻⁴ and the most fragile of forty random matrices 2.5·10⁻⁴, and a code reading only r½ would not know which was which. The pair does: every shooting matrix grows by more than ten times every random one, so the plane of growth against r½ has the random matrices in its bottom right, the shooting matrices above and to their left, and the ties on the left edge.

What a random matrix’s r½ means is less clear, and this essay does not settle it. A growth of 3 can only be halved by noise that changes the matrix, not merely its pivot choices, so the noise-halving measurement has nothing to measure. The small r½ some random matrices record — a few steps where two candidates happen to be within a part in a few thousand — says their pivot sequence is not robust; it does not say their growth is at stake, because there is almost none.

Why a noise sweep is the wrong instrument for a code #

Everything in the table’s last column came from a sweep: fifteen draws of noise at each of up to thirty levels, a factorisation per draw, and the median read off at each level. For the shooting matrix over 12 that is several hundred factorisations to find one number, and the number is a property of a distribution of perturbed matrices rather than of the matrix in hand. One draw in twenty is the standing reminder here of what a single draw of such a distribution does and does not say, and a code cannot afford the other nineteen.

The recording replaces the sweep with the quantity the sweep was estimating. It is read off the factorisation that was going to be computed anyway, it involves no randomness, and it gives the same answer every time the same matrix is factorised. What it gives up is the constant: the sweep measures the noise at which the median growth halves, and the recording predicts it to within a factor of two or three, with the direction of the error — the recording is below the measurement on five of the seven matrices — consistent with the amplification constant being below one.

That trade is the usual one between a measurement and a diagnostic, and the table says it is a good one here: the recorded numbers span the same three and a half decades the measured ones do, in the same order, with no matrix out of place. A code that wants to know whether a large growth factor is a tie, a margin, or nothing to worry about does not need the constant. It needs the order of magnitude and the distinction between zero and not zero, and both are in the record.

What a code could do with it #

Recorded beside the growth factor, r½ turns one number into a reading of what kind of growth it is.

Small growth. Nothing to do, whatever r½ says.

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, and a code could remove it on purpose with a random tie-break. Wilkinson’s construction, which the bound that is never attained measured, is the standard example, and the recording says so when it meets it.

Large growth, r½ well above rounding. The growth rests on a margin and survives every perturbation below r½ — and, as noise the growth amplifies found, every perturbation that keeps the matrix’s zeros, up to the margin itself. It is a property of the matrix. The repair is a pivot rule that does not make the comparison: a pivot that searches one row and one column keeps the shooting matrix’s growth below 2, and a code that switched to rook pivoting only on factorisations recording large growth and a nonzero r½ would pay for the extra search only where it buys something.

That last branch is the one that matters in practice, because it is the case the growth a boundary-value problem supplies found arising from a standard method, and the one a code has no other way to recognise. Its backward error, measured there, is what the growth costs; r½ is what says the cost is not going to go away if the data is slightly different.

What this rests on #

Seven shooting matrices from one boundary-value problem and Wilkinson’s matrix at two sizes, with the halving noise measured on a half-decade grid over fifteen draws, and forty random Gaussian matrices at one size, recorded but not swept. The margin is the relative gap between the two largest candidates in absolute value; a candidate list with ties among the others, or with a second candidate of opposite sign and equal size, gives a margin of zero, which is what Wilkinson’s records.

The prediction’s constant is taken as one. The amplification measurement put the true constant between 0.2 and 0.43, which would move the predicted noise up by a factor of two to five; the half-decade grid and the factor-of-two agreement do not resolve that, and a finer sweep would.

The recording costs one comparison per candidate. It was checked to change nothing about the factorisation: the growth it reports agrees with the full elimination’s to twelve digits on the four shooting matrices it was compared on.

The claim that has to fail #

The claim is the naive recording: the smallest margin over growth anywhere in the factorisation predicts the noise that removes the growth. On the shooting matrix over 12 at 0.3 that minimum is 8.2·10⁻⁹, at step 81, and dense noise of 10⁻⁶ halves the growth — a hundred and twenty times more. The refusal is fed the claim that the unrestricted minimum predicts within a factor of three and fails; r½, read from the same factorisation with the one restriction, predicts within a factor of 0.92.

Still open: several margins, a sparse factorisation, and the constant #

Several growing modes. A transfer matrix with several diagonal entries near one gives several interleaved chains, each with its own margin, sharing columns. Whether r½ still picks out the comparison whose reversal halves the growth, or whether amplified noise from one chain reverses another’s comparison first, decides whether one recorded number is enough.

A sparse factorisation. A sparse code with threshold pivoting does not choose the largest candidate but any within a factor of it, and a threshold between fill and growth measured that trade. 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 constant, measured. A full-resolution sweep of the halving noise on the same seven matrices would say whether the factor between r½ and the halving noise is the amplification constant, 0.2 to 0.43 with the step, or something else — and whether a recording that divides by that constant does better than one that does not.