A worst case is as fragile as its margin

The growth a boundary-value problem supplies found large growth under partial pivoting on a matrix nobody built for it: a multiple-shooting matrix whose growth is the growing mode of its differential equation over the whole interval, switched on by one entry of the transfer matrix falling below one. That puts two worst cases side by side — Wilkinson’s construction, which attains the 2ⁿ⁻¹ bound, and the shooting matrix, which reaches e^(5T/6)/2 — and it invites the question the smoothed analysis of Gaussian elimination was built to ask. If the matrix is perturbed a little, how much of the growth survives?

The expectation that analysis encourages is that worst cases are fragile. A matrix whose growth depends on an arrangement of entries so particular that nobody meets it by accident should lose that growth when the arrangement is disturbed. For Wilkinson’s matrix the expectation is right, in the most extreme way available: noise at the level of the last digit a double can hold removes eleven orders of growth. For the shooting matrix it is right in form and wrong in size, by a factor of about ten million.

What separates them is not how large the growth is but what it rests on, and that is a number. Each worst case is held up by a comparison partial pivoting makes at every step, and each comparison has a margin — zero for Wilkinson’s ties, 5.6·10⁻³ for the shooting matrix’s near-tie. The growth survives noise smaller than its margin, and above it the median growth is the margin divided by the noise.

Two worst cases and what holds each up #

Wilkinson’s matrix has ones on the diagonal, minus ones below it and a column of ones on the right. At every step of the elimination the candidate pivots in the column are a one on the diagonal and minus ones below, all of the same size. Partial pivoting takes the first of equal candidates, which is the diagonal, makes no interchange, and the last column doubles. The growth rests on those ties being exact: the bound that is never attained observed that the rule “has nothing to choose, does exactly what it is supposed to, and the entries double anyway”, and it is the having nothing to choose that noise removes.

The shooting matrix has, at every continuity step, a choice between the diagonal entry of the transfer matrix, $E_{11}$ = 0.99436 at a step of 0.3, and a −1 in the same column. The two are not equal. Partial pivoting takes the −1, which is larger by 5.6·10⁻³, and that choice is what carries the boundary condition’s coupling down the chain and multiplies it by the growing mode at every step. A perturbation smaller than the margin cannot reverse the comparison; one larger than the margin can, at some steps, and each reversal breaks the chain there.

So the two matrices are the two ends of one scale. A tie is a margin of zero. A choice decided by five thousandths of the entries’ size is a margin of five thousandths. The measurement is whether the noise a worst case can absorb is set by that number.

Wilkinson’s growth does not survive the last digit #

With no noise the growth is 2³⁹ = 5.5·10¹¹. With Gaussian noise of standard deviation 10⁻¹⁶ — half a unit in the last place of a double near one — the median growth over thirty draws is 2. The worst of the thirty is 8. At 3·10⁻¹⁶ and 10⁻¹⁵ the median is 2 and the worst 16; from 3·10⁻¹⁵ on, not one draw exceeds 2. Below the rounding level the noise mostly rounds away: at 10⁻¹⁷ the median growth is still 128 and the worst 2,048, because an added 10⁻¹⁷ does not change the stored value of a one, and whether it changes a minus one depends on the draw.

The growth of 2 that remains is itself a statement about ties. With every tie broken in a random direction, about half the steps choose a subdiagonal entry and interchange rows, and an interchange stops the doubling of the last column at that step. What survives is the doubling at the final step or two, which no interchange can reach. A partition decided in the last digit found a discrete decision in another algorithm resting on the last digit of a double in the same way, and the moral carries: an output that depends on a tie is an output of the tie-breaking rule, and the tie-breaking rule is whatever the rounding makes it.

From 10⁻² the median drops a little below 2 — 1.98 at 10⁻², 1.87 at 10⁻¹ — as the noise begins to change the entries’ sizes rather than only their order, and at σ = 1 the matrix is a random one with a median growth of 2.85, of the order the first growth essay measured for random matrices of this size.

The shooting matrix’s growth survives ten million times more #

The same thirty draws on the shooting matrix give a different curve.

Up to 10⁻⁸ the median growth is 1.1·10⁴ — unchanged to four figures — and the worst of thirty at 10⁻⁸ is within a fifth of a per cent of it. At 10⁻⁷ it is still 1.10·10⁴. The noise that took Wilkinson’s growth from 5.5·10¹¹ to 2 is seven orders of magnitude below the noise the shooting matrix ignores.

From 10⁻⁶ the growth begins to fall, and it falls in a straight line on logarithmic axes: 4.8·10³ at 10⁻⁶, 536 at 10⁻⁵, 54 at 10⁻⁴, 5.8 at 10⁻³, and 2.0 at 3·10⁻³. A factor of ten in the noise costs a factor of ten in the growth, and the line lands on 2 at about half the margin.

The factor shows the mechanism. With noise of 10⁻⁶, on one draw, the rows of U climb along the continuity chain exactly as they do with no noise, until they reach 2,933 times the matrix’s largest entry, and then stop climbing: somewhere along the chain the noise has reversed one comparison, partial pivoting has taken the transfer matrix’s entry instead of the −1, and the coupling the corner started no longer rides the chain past that step. The growth that remains is the growing mode over the stretch of the chain before the first reversal.

At 10⁻⁴ the climb stops at 186. The larger the noise, the sooner along the chain some comparison is reversed, and the shorter the stretch of growing mode the factor accumulates. That is why the median growth falls as the noise rises rather than collapsing at one threshold: the growth is the growing mode over the expected distance to the first reversal, and that distance shrinks as the noise approaches the margin.

Growth is the margin over the noise #

If the growth is set by how soon a reversal comes, and a reversal needs the noise to overcome the margin, the growth should be the margin divided by the noise. The shooting matrix can be built with different margins by changing the step — at a step of 0.1 the margin is 1.2·10⁻², at 0.2 it is 1.3·10⁻², at 0.25 it is 1.1·10⁻² and at 0.3 it is 5.6·10⁻³ — and the prediction tested at each.

Across the four steps and eight noise levels from 10⁻⁶ to 3·10⁻³, the median growth times σ divided by the margin lies between 0.50 and 1.35. At a step of 0.1 it stays between 0.50 and 0.66; at 0.2 between 0.62 and 1.11; at 0.25 between 0.75 and 1.04; at 0.3 between 0.74 and 1.35. The form — growth proportional to margin over noise — holds at every step. The constant is of order one and depends on the step by about a factor of two, which is the part of the prediction the simple argument does not supply: it depends on how the reversals are distributed along the chain, and a step of 0.1 has three times as many continuity rows over the same interval as a step of 0.3.

At a step of 0.2 the margin is 2.4 times the margin at 0.3 and the growth under the same noise is roughly twice as large along the whole line: 1,190 against 536 at 10⁻⁵, 115 against 54 at 10⁻⁴. The two growths start from the same 1.1·10⁴, because the interval is the same, and the step only changes how much noise it takes to bring it down.

Why the constant is not one number #

The margin law holds in form at every step and not in its constant, and the way the constant moves is worth reading, because it says what the simple argument leaves out.

At a step of 0.1 the growth times σ over the margin sits between 0.50 and 0.66 across the whole range of noise; at 0.3 it sits between 0.74 and 1.35. The two matrices describe the same interval, so the growing mode they can accumulate is the same 1.1·10⁴, and their margins are within a factor of two of each other. What differs is how many continuity rows each has: 120 at a step of 0.1 and 40 at a step of 0.3. Every row is a comparison the noise can reverse, and a reversal anywhere along the chain ends the accumulation there. A matrix with three times as many comparisons over the same interval gives the noise three times as many chances to break the chain early, and the expected stretch of growing mode before the first reversal is shorter — so the same ratio of margin to noise buys less growth. That reading predicts the ordering of the four constants, smallest at the finest step, and it predicts the direction of the spread within each; it is consistent with the measurement and is not established by it, since the margins also differ between the steps and the two effects are not separated.

There is a second reason the constant cannot be a universal number, and it is in the margin itself. The margin is the gap between one and $E_{11}$, and $E_{11}$ is an average of the growing mode and the decaying mode over one step. As the step shrinks towards zero the two modes barely move, $E_{11}$ approaches one from below, and the margin shrinks with the step: it is largest near a step of a sixth and falls to zero both at the switch, where $E_{11}$ crosses one, and in the limit of a very fine grid. So the finest shooting grids are fragile again, for the same reason Wilkinson’s matrix is — their comparisons approach ties — and the robust growth measured here belongs to the moderate steps a user would actually take.

That is the sense in which the growth a boundary-value problem supplies and this measurement together describe one number rather than two. The growth is decided by which side of one the transfer matrix’s entry falls, and its robustness by how far from one it falls. A problem, a method and a step size supply both; the elimination supplies neither and inherits both.

What this says about perturbing worst cases #

The smoothed analysis of Gaussian elimination bounds the growth of a matrix perturbed by Gaussian noise in terms of the noise’s size and the dimension, and its conclusion — a worst case is a set of measure zero that a random perturbation escapes — is what both curves confirm. The measurement adds the scale.

A worst case built on ties is as fragile as a floating-point number. Wilkinson’s growth needs every candidate pivot to be exactly equal, and the noise that breaks that is the noise any computation adds by being carried out: one unit in the last place. What a float can hold is the reminder that the digits past that place are not stored, and a growth that depends on them is not a property of the matrix a machine holds.

A worst case built on a margin is as robust as the margin. The shooting matrix’s growth needs one comparison to go one way at every step, by five thousandths, and noise below that leaves it intact however many steps there are. A problem that produces such a matrix does not produce it approximately; it produces it with a margin set by the physics, and modelling error of the size a real computation carries — rounding, discretisation, measurement — is far below that margin.

The robust worst case is the one from practice. That inverts the comfortable reading of the smoothed analysis. The constructed worst case, the one used to show the bound is attained, is the fragile one. The worst case that arrives from a standard method for a standard problem has a margin, and noise that would erase the construction does nothing to it. The swap that is not optional found the absence of a row interchange destroying an answer silently; here it is the presence of a margin that keeps partial pivoting making the same silent choice at every step, and only a rule that searches further, one row and one column at least, stops making it.

A margin as a diagnostic #

The measurement suggests a quantity a solver could compute for itself, and it is worth saying what it would and would not tell.

At each step partial pivoting finds the largest entry in the column and, in doing so, also finds the second largest. Their relative difference is that step’s margin. A factorisation that records the smallest margin along with the growth factor would know, for free, whether its growth rested on near-ties — and a growth that rests on near-ties is the kind the shooting matrix has: stable against perturbation, systematic, and removable by a different pivot rule. A large growth with large margins everywhere would be a different animal, and a small growth with tiny margins would warn that a slightly different matrix might grow a great deal.

What the margin would not tell is whether the growth matters. The exact answer to a nearby problem is the collection’s framing of that question, and here the shooting matrix’s growth of 1.3·10⁵ cost four and a half digits of backward error — enough to notice and not enough to lose an answer. The margin says whether a growth is an accident of rounding or a property of the matrix; the backward error says what it costs; and one draw in twenty is the reminder that thirty draws say what a median does and a single run says what one draw did.

What was not measured #

Two matrices, one noise distribution — independent Gaussian entries of equal standard deviation — and one pivot rule under noise. Noise that respects structure, perturbing only the entries the problem has and leaving the zeros zero, is closer to what a discretisation error does to a shooting matrix, and it may reverse fewer comparisons than dense noise that fills every zero. The margin law’s constant was measured at four steps of one interval and one differential equation; whether it depends on the interval, on the ratio of the two modes’ rates, or only on the number of continuity rows is not separated. And the margin is measured as $E_{11}$ against one, which is the margin of the comparison that matters here; a matrix whose growth rests on several different near-ties would have several margins, and which of them sets the noise it can absorb is not tested.

Still open: structured noise, the margin a solver can record, and several near-ties #

Noise that keeps the zeros. Perturbing only the nonzero entries of the shooting matrix — E and the −1s — is what a slightly wrong transfer matrix does, and the measurement is whether the growth follows margin over noise with the same constant or with a larger one, since the only comparisons structured noise can reverse are the ones along the chain.

Recording the margin. A partial-pivoting routine that returns the smallest relative gap between the largest and second-largest candidate at any step, beside the growth factor, and a sweep over random, constructed and practical matrices showing how that pair of numbers separates the fragile worst cases from the robust ones, would turn this measurement into a check a code could run on every factorisation.

Several margins. A system of differential equations with several growing modes gives a transfer matrix with several diagonal entries near one, and so several near-ties with different margins at every step. Whether the growth under noise then follows the smallest margin, the largest, or a combination is the question that decides whether a single recorded margin is enough.