The growth a boundary-value problem supplies

The bound that is never attained set out the growth factor’s standing problem. Partial pivoting permits the entries of a factorisation to double at every step, one matrix built by Wilkinson attains that exactly, random matrices come nowhere near it, and the reason nobody worries is empirical: growth factors above ten are essentially never seen on matrices from applications, and matrices that produce large growth have to be constructed. The essay ended on the open question of why, and on the argument for measuring rather than assuming.

The empirical half of that argument has a well-known exception, and it is not a construction. A two-point boundary-value problem for a linear system of differential equations, discretised by multiple shooting — one of the standard ways to solve such a problem — produces a matrix on which partial pivoting’s growth is exponential in the length of the interval. Wright published the example; this essay measures it, and finds three things the citation leaves out.

The growth is not approximately exponential but exactly the growing mode of the differential equation, halved. It sits on a matrix whose condition number is single-digit throughout, so it is growth the problem does not contain. And it appears only when the shooting grid is fine enough: there is a step size below which partial pivoting’s choice at every continuity row flips to the entry that accumulates, and above which the same method on the same problem has no growth at all.

A matrix from a method, not from a construction #

The problem is the system y′ = My on an interval [0, T] with

$$M = \begin{bmatrix} -1/6 & 1 \\ 1 & -1/6 \end{bmatrix}$$

and the boundary condition y(0) + y(T) = β. M has eigenvalues 5/6 and −7/6, so the equation has one mode that grows like e^(5t/6) and one that decays like e^(−7t/6). A boundary-value problem of this kind is well posed — the boundary condition pins down the growing mode — and is the ordinary situation for a system with modes in both directions.

Simple shooting integrates from 0 to T and fails, because the growing mode swamps everything over a long interval. Multiple shooting breaks the interval into N steps of length h, takes the state at each of the N + 1 points as an unknown, and asks for continuity between them: $s_1 = E s_0$, $s_2 = E s_1$, and so on, where E = exp(hM) is the transfer matrix over one step, exact here because M is constant. With the two boundary equations, that is a linear system in 2(N + 1) unknowns:

$$\begin{bmatrix} I & & & I \\ E & -I & & \\ & \ddots & \ddots & \\ & & E & -I \end{bmatrix} \begin{bmatrix} s_0 \\ s_1 \\ \vdots \\ s_N \end{bmatrix} = \begin{bmatrix} \beta \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$

The matrix is block bidiagonal apart from the corner the boundary condition puts in the top row, its entries are bounded by the entries of E and one, and it is nothing like Wilkinson’s matrix. It is the linear system a textbook method writes down.

The growth is the growing mode, halved #

At a step of h = 0.3 and intervals from 1.5 to 15, the growth factor under partial pivoting is:

From T = 12 the growth equals e^(5T/6)/2 to four figures, and at T = 6 it is 1.3 per cent above it. The exponent 5/6 is the growing mode’s rate. The factor of one half is the diagonal of E averaging the growing and decaying modes along the continuity chain. So the growth factor of the elimination is a quantity the differential equation specifies before any matrix is formed: how much the growing mode amplifies over the interval.

The condition number meanwhile is at most 8.3. The matrix is not ill conditioned and does not become so — it rises from 4.7 to 8.3 while the growth rises by four orders — so the boundary condition does what it is supposed to do and pins the growing mode. The growth is not the problem’s difficulty expressed in the factorisation. It is the factorisation’s own.

Rook and complete pivoting keep the growth below 2 at every interval. A pivot that searches one row and one column found rook pivoting holding Wilkinson’s matrix at exactly 2 for about three times partial pivoting’s search; on the shooting matrix the rook’s growth is the same as complete pivoting’s to four figures at every size. Moving the boundary rows from the top of the matrix to the bottom changes nothing: 7.1, 905 and 1.34·10⁵ again at T = 3, 9 and 15.

Where in the factor it accumulates #

The table gives one number per matrix. The factor shows where the number comes from.

Under partial pivoting the rows of U climb through the continuity equations one step of the growing mode at a time and reach their largest entry, 1.1·10⁴ times the largest entry of the matrix, in the last rows. The mechanism is the corner. The boundary row couples $s_0$ to $s_N$, and eliminating down the chain carries that coupling through every continuity row, multiplied at each step by the transfer matrix’s entry — so by the time the elimination reaches $s_N$, the entry that began as a one in the boundary row has been multiplied by the growing mode over the whole interval. That is the same shape as Wilkinson’s matrix, in which the last column doubles down the rows, with the growing mode’s factor per step in place of two.

Complete pivoting takes its pivots from the continuity equations’ −1 entries in a different order, never lets the corner’s coupling ride the chain, and no row of its U exceeds twice the matrix’s largest entry.

The finer grid is the one that grows #

The step size is a choice, and it is the choice that decides whether there is any growth at all.

At T = 12, every step from 0.1 to 0.333 gives a growth of 1.1·10⁴, and every step from 0.353 to 0.5 gives a growth under 2. There is nothing in between. The switch sits at h = 0.3397, the step at which the diagonal entry of the transfer matrix,

$$E_{11} = \tfrac12\left(e^{5h/6} + e^{-7h/6}\right),$$

is exactly one. At each continuity row partial pivoting compares $E_{11}$ with the −1 below it in the same column. When $E_{11}$ is larger — a coarse step, over which the growing mode has had room to grow — the continuity row’s E entry is the pivot and nothing accumulates. When $E_{11}$ is smaller — a fine step, over which the decaying mode still pulls the diagonal below one — the −1 is the pivot, the multiplier is $E_{11}$ over −1, and the corner’s coupling is carried on down the chain.

At T = 6 the picture repeats with the growth at 75.2, the growing mode over the shorter interval. The switch is at the same step, because it is a property of one step of the transfer matrix and not of the interval. So a user who refines the shooting grid for accuracy — the usual reason to take more steps — crosses from a factorisation with no growth into one whose growth is the whole interval’s amplification, at a step size set by the differential equation’s two rates and nothing else.

That runs against the grain of how shooting is usually tuned. Shorter steps make each continuity equation better conditioned, and multiple shooting exists because long steps are dangerous. On this problem a step of 0.4 gives a factorisation whose growth is under 2, and a step of 0.3 gives one whose growth is 1.1·10⁴, with both matrices well conditioned.

At a step of 0.4 the growth under partial pivoting is 1.98 at T = 15.2 — identical to rook and complete pivoting — and the condition number at most 6.9. At a step of 0.2, below the switch, it is 1.34·10⁵ at T = 15 on 152 unknowns, with a condition number of 12, the same growth as at 0.3 because the growth belongs to the interval and not to the number of steps it is divided into.

What the growth costs the solve #

A growth factor matters because the backward error is bounded by about n times the growth times the unit roundoff. On this matrix the bound’s middle factor is 1.3·10⁵, and the measurement is how much of that the solve actually pays.

Under partial pivoting the backward error rises from 5.7·10⁻¹⁷ at T = 1.5 to 1.35·10⁻¹² at T = 15 — four and a half digits lost against complete pivoting, which stays at 5.9·10⁻¹⁷ throughout. The bound n·ρ·u is 1.5·10⁻⁹ at T = 15, so the solve pays about a thousandth of what the growth permits: the bound multiplies every pessimism together, and the rounding errors do not all land along the direction the growth amplifies.

The forward error at T = 15 is 8.0·10⁻¹² under partial pivoting and 1.7·10⁻¹⁶ under complete, on a matrix whose condition number of 8.3 amplifies a backward error by at most that. A small residual is not a small error put the standing distinction between the two kinds of error; here both are the algorithm’s, the problem is innocent, and the backward stability that the first growth essay described as the flat line everything rests on is bent by four and a half digits by a matrix nobody designed. On a double-precision machine that leaves eleven correct digits, which is enough for most purposes and is not the sixteen a well-conditioned system is entitled to.

A rule that is right at every step and wrong for the chain #

The shooting matrix’s growth is worth a closer look at the level of a single step, because every step partial pivoting takes on it is a good one by the rule’s own standard.

Partial pivoting’s guarantee is local. At each step it takes the largest entry in the column as the pivot, so every multiplier is at most one in size, and the swap that is not optional showed what goes wrong without that: a multiplier of 10¹⁷, an answer of the right shape and nothing to announce the failure. On the shooting matrix below the switch, every multiplier partial pivoting forms along the continuity chain is $E_{11}$ over −1, which is 0.994 in size at a step of 0.3. The rule’s promise is kept at every step. The growth comes from the fact that the promise is about one step, and a chain of steps each multiplying the corner’s coupling by a number just under the growing mode’s factor compounds the way a chain of doublings does in Wilkinson’s matrix.

Elimination is a sequence of choices described the decision at each step as the whole of the algorithm’s stability, and this is the case where the decisions are individually sound and collectively the worst available. Complete and rook pivoting see more than the column. Their search reaches the rows below and the columns to the right, finds entries that break the chain, and the corner’s coupling never gets to ride it. That is the reason the rook, which searches one row and one column rather than the whole remaining matrix, removes all of the growth here: the chain is a structure in one row and one column at a time, and a search of that width is enough to see it.

The comparison partial pivoting makes is also a comparison of two numbers whose relative size is set by how the equations were written. $E_{11}$ and −1 sit in the same column because the state at one point appears in two continuity equations, once as E times itself and once as minus itself. The pivot that reads the units found a row scaling that made partial pivoting perform the elimination it exists to prevent, with no interchange at all, on the standard two-by-two example. The shooting matrix’s switch is the same vulnerability in a longer form: which side of one the diagonal entry of E falls on decides the whole factorisation, and a solver that scaled its continuity equations differently would put the switch somewhere else. Where exactly is a measurement this essay did not make.

None of this shows in the condition number, and it could not. The condition number is a property of the matrix, invariant under the choices the elimination makes, and the condition number as an amplifier describes what it bounds: how much the problem magnifies an error the algorithm introduced. Here it magnifies by at most 8.3, and the algorithm introduced 1.35·10⁻¹² of backward error where it could have introduced 6·10⁻¹⁷.

What this does to the empirical argument #

The bound that is never attained offered two reasons nobody worries about growth: structural classes where it cannot happen, and an empirical record in which it does not. The shooting matrix belongs to no structural class — it is not symmetric, not diagonally dominant, not totally nonnegative — and it is a counterexample to the empirical record that the record’s own literature contains. It sharpens that argument in three ways rather than overturning it.

Growth that arrives from a problem has a mechanism, and the mechanism is a margin. The growth appears exactly when one entry of the transfer matrix falls below one, and it is the growing mode over the interval. That is a far more specific object than “a matrix constructed to produce growth”, and it says where to look in other problems: wherever an elimination’s pivot choice at each step of a chain is decided by a near-tie between an entry that carries a growing quantity and one that does not.

The condition number says nothing about it. Every matrix here has κ between 4.7 and 12. A user who checks the conditioning, finds it excellent and concludes the solve is safe has checked the problem’s property and not the algorithm’s — the same separation the exact answer to a nearby problem draws for every backward-stability argument.

The fix is cheap and known. Rook pivoting removes the growth entirely at a few times partial pivoting’s search, and a solver for boundary-value problems can order the unknowns or pivot within the block structure so that the corner’s coupling never rides the chain. The empirical argument survives as a statement about unstructured matrices; structured ones from methods with chains in them deserve the one extra comparison per step the first growth essay recommended.

What was not measured #

One differential equation, with one growing and one decaying rate; a system with several growing modes, or with modes whose rates are close, would move the switch and possibly split it into several. Only the boundary condition y(0) + y(T) = β; separated boundary conditions, which put the growing mode’s constraint at one end only, change the corner and may change the growth. And only dense partial pivoting; a sparse or banded solver for the shooting matrix would take the continuity structure into account in its ordering, and whether the switch survives a banded elimination with threshold pivoting is not drawn.

Still open: noise, several growing modes, and a band solver #

What noise does to growth that rests on a margin. Wilkinson’s growth rests on exact ties between candidate pivots; the shooting matrix’s rests on a margin — $E_{11}$ against one, a difference of 5.6·10⁻³ at a step of 0.3. A worst case is as fragile as its margin measures what random perturbations of every size leave of each, and finds that the two kinds of growth need noise of very different sizes to disappear.

Several growing modes. A system with modes growing at different rates has a transfer matrix whose diagonal entries cross one at different steps, and the growth may switch on in stages as the step is refined. Whether the growth then follows the fastest mode alone, or a product of the modes whose entries have crossed, is the measurement.

A band solver. The shooting matrix is banded apart from its corner, and a band solver with partial pivoting within the band handles the corner by bordering. Whether that arrangement inherits the growth — whether the switch at $E_{11}$ = 1 is a property of the matrix or of dense partial pivoting on it — is the question a practitioner choosing a solver would ask first.