A trigger finer than the growth

A threshold that holds the growth still found that a sparse code’s pivot rule reproduces partial pivoting’s growth exactly on the two matrices the argument about growth has been built on. The multiple-shooting matrix a boundary-value problem supplies grows by $e^{5T/6}/2$ under partial pivoting — $1.1 \cdot 10^4$ over an interval of 12 — and it grows by the same amount under threshold pivoting at every τ from 1 to 0.1, because at τ = 1 threshold pivoting is partial pivoting and below it the choice is held by row counts that no perturbation of the values can move. Raising the threshold cannot help. Only a search that looks along a row as well as down a column, as a pivot that searches one row and one column measured, keeps the growth below two.

The essay’s last question was whether a factorisation could get rook pivoting’s protection without paying rook pivoting’s price everywhere. A factorisation already knows its growth as it goes: it has just written every entry of the active submatrix. If it recorded large growth on a step, it could search as rook pivoting does for the steps that follow and search as partial pivoting does otherwise, paying for the stricter search only where growth is being made. Whether that removes the shooting matrix’s growth or only moves where it happens was the open measurement.

It removes it, and the reason it can is the reason the proposal is misdescribed. The shooting matrix never makes large growth on any step.

Growth made a little at a time #

Drawn step by step on a logarithmic axis, partial pivoting’s growth on the shooting matrix is a staircase with even treads. Over 82 elimination steps it rises from one to $1.1 \cdot 10^4$ in about forty rises, one on every other step, which reach their full size within the first fifth of the elimination and stay there; none of them is large. Rook pivoting stays below 1.3 until the last few steps and ends at 2.00. The third line is the proposal with a sensitive trigger: partial pivoting, except that a step following one which multiplied the active submatrix’s largest entry by more than 1.1 searches as rook pivoting does. It ends at 2.00, identical to rook pivoting’s, having searched as rook on 39 of the 82 steps.

The rises are the whole story. At a shooting step of 0.3 every other elimination step multiplies the largest entry by exactly 1.284, and the steps between multiply it by exactly one. At 0.2 the rise is 1.181; at 0.15, 1.133. Those numbers are $e^{5h/6}$ to four figures — the growth of the boundary-value problem’s increasing mode over one shooting interval. The growth a boundary-value problem supplies derived the total, $e^{5T/6}/2$, from that mode; what the step-by-step picture adds is that the elimination makes the total in exactly the pieces the problem is cut into. Each shooting interval contributes two rows, one of which carries the growing mode’s step forward, and partial pivoting’s choice between the interval’s diagonal entry and the $-1$ below it — the margin of $5.6 \cdot 10^{-3}$ the margin essays recorded — puts that step’s growth into the active submatrix.

So a finer shooting grid makes the same growth in more, smaller rises. Over an interval of 12 the total is $1.1 \cdot 10^4$ at every step length measured; at a step of 0.15 it is made in about seventy-five rises of 1.133.

The trigger has to be finer than the growth #

Sweep the trigger’s sensitivity. At a shooting step of 0.3, every sensitivity from 1.02 to 1.2 holds the growth at 2.00, and 1.25 holds it at 2.30. At 1.3 the trigger never fires — no step rises by more than 1.284 — and the growth is partial pivoting’s, $1.1 \cdot 10^4$, to the last digit. There is nothing in between: the trigger either sees every step of the staircase or none. Turn the dial to a step of 0.2 and the edge moves to between 1.15 and 1.2, straddling 1.181; at 0.15 it is between 1.1 and 1.15, straddling 1.133. In every case the trigger catches the growth exactly when its sensitivity is below the growing mode’s rate over one interval, and misses it completely above.

That is a condition a code cannot check in advance. The rate belongs to the differential equation and the shooting grid, not to the matrix a solver receives, and a solver that wanted to catch every such problem would need a sensitivity below the rate of the finest grid anyone might use. At a step of 0.05 over the same interval that rate is 1.043; the total growth would be the same $1.1 \cdot 10^4$.

Why one rook step undoes one rise #

The trace of the sensitive trigger is flat, and the reason is exact. Under the trigger at a shooting step of 0.3, every step searched as partial pivoting multiplies the active submatrix’s largest entry by 1.283 or 1.284, and every step searched as rook multiplies it by 0.779 or 0.780 — which is $1/1.284$. The rook step does not merely stop the next rise. It picks, from the row the growing entry sits in, a pivot that divides it back out, so the pair of steps multiplies the largest entry by one to three decimals. The growth so far is 1.284 after the first rise and it is 1.284 at step 40; it becomes 2.00 only at the last two steps, where the boundary rows are eliminated and rook pivoting’s own growth appears. At a shooting step of 0.15 the pattern is the same with smaller factors, 1.12 to 1.133 up and 0.882 to 0.897 down, and the growth holds at 1.48.

That is the sense in which a sensitive trigger costs about two thirds of rook’s extra search and buys all of rook’s protection: on this matrix, rook pivoting’s advantage is delivered on alternate steps, one division for one multiplication, and a search that turns rook on exactly those steps has reproduced it. It is also why the trigger is all or nothing. A rise the trigger does not see is a rise no rook step undoes, and every rise it does not see is the same size as every other.

The bound that is never attained set partial pivoting’s guarantee of $2^{n-1}$ beside the growth random matrices actually show, about three at forty. The shooting matrix sits between them on a staircase of its own, and the staircase’s steps are small enough to be missed and regular enough to be undone one at a time.

What a sensitive trigger costs #

Counted as matrix entries examined by the search, rook pivoting on every step costs exactly three times partial pivoting on the shooting matrices: one column scan becomes a column scan and two row scans at every step. A trigger fine enough to catch the growth costs between 1.74 and 1.93 times partial pivoting — about two thirds of rook’s extra — because it searches as rook on about half of the steps: every step that follows a rising one, which on this matrix is every other step. A trigger coarse enough to cost nothing catches nothing.

The price is not where the growth is. The trigger fires on every other step from the first rise to the last, on steps where the growth so far is two and steps where it would have been ten thousand, because each rise looks the same. A factorisation that paid for rook’s search “only where growth is being made” pays for it on half the matrix, since growth is being made on half the matrix, a little at a time.

A trigger on ordinary matrices #

The price on the shooting matrix buys a factor of five thousand in growth. The same trigger on a matrix that did not need it buys much less.

On forty Gaussian matrices of order forty, partial pivoting’s median growth is 3.21 and its largest 4.81; rook pivoting’s are 2.09 and 2.87, at 3.31 times the search. A trigger at 1.1 — fine enough for the shooting matrix at a step of 0.3, not for 0.15 — searches as rook on a quarter of the steps of the median matrix and costs 1.67 times partial pivoting’s search, and brings the median growth to 2.64. At 1.02 it fires on 43 per cent of the steps. At 1.3 it fires on 7.5 per cent and the median growth is 2.90. On a random matrix the active submatrix’s largest entry fluctuates by tens of per cent from step to step for no reason that matters, and a trigger cannot tell those fluctuations from the start of a staircase.

Coarse triggers are worse in a way the figure shows at the top. At sensitivities of 2 and 4 the trigger fires rarely, and on one of the forty matrices the steps it chooses make the growth 6.86 — larger than partial pivoting’s worst, 4.81. Switching rules part-way through an elimination is not guaranteed to land between the two rules’ growth; a rook step that picks a different row changes every comparison partial pivoting makes afterwards. The median is not harmed. The worst case is.

A latch on the total instead #

The other form of the proposal records the total rather than the step: once the growth so far reaches a level g, every later step searches as rook does.

A latch sees the shooting matrix’s growth whatever the step length, because the total is large even when no step is. And it does what a latch should: the growth stops at its level. On the shooting matrix at a step of 0.3 a latch at 16 ends at 16.6, at 64 at 74.2, at 256 at 259 — between the level and three tenths above it at every level. On Wilkinson’s matrix of forty, whose growth doubles at every step to $5.5 \cdot 10^{11}$, it ends at the level exactly.

What it costs is everything after the latch closes. On the shooting matrix a latch at 16 closes at step 28 and searches as rook on the 54 steps that remain, 1.87 times partial pivoting’s search in all; a latch at 2 costs 2.46 and still leaves growth of 2.30, above rook’s 2.00. Because the staircase is even, the latch’s saving on the search is roughly the share of the staircase below its level — a level of 256 closes three fifths of the way through and costs 1.31. The latch trades search for growth at a fixed rate, and the growth it accepts is its own level, chosen in advance.

What the proposal was reaching for #

The proposal was to pay for the stricter search only where growth is being made, and on the shooting matrix that is everywhere: forty equal rises over eighty-two steps. The cost of preventing that growth is therefore close to the cost of rook pivoting over the whole elimination, whichever trigger is used — two thirds of rook’s extra search for the step trigger, all of it after the level for the latch — because the growth is not localised. A trigger could pay only where growth is made if growth were made in a few large steps, and the one matrix in this collection that makes it that way, Wilkinson’s, doubles at every step and is caught by any trigger below two.

The step trigger does reach Wilkinson’s matrix too. At sensitivities of 1.1 and 1.5 it fires on twenty of forty steps and ends at 4, not 2. A trigger acts on the step after the rise it reads, so it is always one rise late, and on a matrix that doubles at every step one rise is a factor of two.

So the question the preceding essays have been asking — whether a growth factor is a property of the matrix or an accident of the rule, which a worst case is as fragile as its margin first put as a question about noise — gets one more answer. Under partial pivoting and under any threshold, the shooting matrix’s growth is a property of the rule, because rook pivoting removes it. It is not a property the rule can detect cheaply, because it is made of forty moderate steps rather than one large one. Noise the growth amplifies found the stored noise multiplied by the growth already made; what the trigger measurements add is that the growth already made, at any step, is a small fraction of the final growth, and so is any warning a factorisation could give on the way.

A latch states a guarantee, a step trigger guesses a time scale #

Three things the measurements support.

A latch is a guarantee a code can state. “The growth factor is at most about g, and if it would have exceeded g the factorisation searched as rook pivoting does from then on” is a sentence a solver could print. It costs rook’s search on the part of the elimination after the latch, which on a matrix that does not grow is nothing, since the latch never closes: on the forty Gaussian matrices a latch at four or above never closes on the median matrix, and a latch at two closes on it and searches as rook on 29 of its 40 steps.

A step trigger is a guess about the problem’s time scale. It works when its sensitivity is below the rate at which the problem’s growing mode acts per row of the matrix, and that rate is a property of how the problem was discretised. A code that knew it was solving a shooting system could set the trigger from the shooting step. A general-purpose code cannot.

Neither is the backward error. The growth factor bounds the backward error from above, and a margin the factorisation records and its successors read the growth as a property worth reporting. The standard safeguard in a code that does not pivot strictly is still to compute the backward error and refine, as a threshold between fill and growth found necessary. A latch at g changes what that check will find, not whether it is needed.

One growing mode, one Wilkinson matrix, forty Gaussians #

One boundary-value problem, whose transfer matrix has a single growing mode, at three shooting steps over one interval; Wilkinson’s matrix of forty; and forty Gaussian matrices of forty. The step trigger reads the active submatrix’s largest entry, which a dense factorisation has for free and a sparse one would have to maintain; the latch reads the growth so far, which both have. The cost is counted in entries examined by the search, not in time, and a rook search’s row scans touch memory that a column-oriented code stores badly, so the real price of a rook step is higher than its count.

The Gaussian matrices’ worst case under a coarse trigger, 6.86, comes from one matrix of forty; the claim is only that switching rules part-way can exceed both rules’ growth, not how often.

Still open: a trigger that reads the interval, and several growing modes #

A trigger over a window. The step trigger fails on fine grids because each rise is small, and the latch fails to save anything because it waits for the total. A trigger on the growth over the last w steps — the product of w rises — would see a staircase of small rises as one large one while ignoring a random matrix’s fluctuations, which do not compound. The prediction with a sign is that a window of ten steps and a level of two catches the shooting matrix at every step length measured and fires on under five per cent of a Gaussian matrix’s steps.

Several growing modes. A boundary-value problem with several growing modes, at different rates, gives several staircases interleaved. A step trigger set for the fastest misses the slowest; a window trigger would see their product. How many rook steps it takes to hold several chains at once, and whether one chain’s rook step changes another’s comparisons — the question the threshold essay left about counts — is the direct continuation.

Where the backward error sits under a latch. A latch at g guarantees growth near g. Whether the backward error of the resulting solve is then near $g u$ times the problem’s size, as the bound allows, or near rook pivoting’s, which is the more useful sentence for a code to print, is a measurement on the same matrices with the exact solution to hand.