Growth factor under partial pivoting to n = 40: the bound, the worst case, and reality
At its defaults it draws growth factor under partial pivoting to n = 40: the bound, the worst case, and reality. Growth factor against matrix size on a logarithmic vertical axis. The two-to-the-n bound rises as a straight line; Wilkinson's matrix sits exactly on it; random matrices stay near one.
growth-factor is one function in lib/figures/elim.js —
elimination — the swap, the growth factor, and the matrix with a known answer. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
Growth factor against matrix size on a logarithmic vertical axis. The two-to-the-n bound rises as a straight line; Wilkinson's matrix sits exactly on it; random matrices stay near one.
show: "margin-predict"
The arguments are the ones A margin the factorisation records passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For multiple-shooting matrices over intervals of 6, 9, 12 and 15 at steps from 0.15 to 0.3, the recorded quantity r½ — the smallest pivot margin divided by the growth reached so far, over the steps before half the final growth had arrived — against the smallest Gaussian noise, on a half-decade grid, at which the median growth over fifteen draws is at most half the noise-free growth, on logarithmic axes. The diagonal is equality and the band a factor of three either way. shooting, T = 6, h = 0.3: growth 75.2, r½ 1.61·10⁻⁴, measured 3.2·10⁻⁴; shooting, T = 9, h = 0.3: growth 905, r½ 1.32·10⁻⁵, measured 3.2·10⁻⁵; shooting, T = 12, h = 0.3: growth 11000, r½ 1.08·10⁻⁶, measured 10⁻⁶; shooting, T = 15, h = 0.3: growth 1.3·10⁵, r½ 8.9·10⁻⁸, measured 10⁻⁷; shooting, T = 12, h = 0.25: growth 11000, r½ 2.23·10⁻⁶, measured 3.2·10⁻⁶; shooting, T = 12, h = 0.2: growth 11000, r½ 2.79·10⁻⁶, measured 3.2·10⁻⁶; shooting, T = 9, h = 0.15: growth 905, r½ 3.21·10⁻⁵, measured 3.2·10⁻⁵. Wilkinson's matrices record r½ = 0 and lose half their growth at noise of 10⁻¹⁶, off this chart.
show: "margin-trace"
The arguments are the ones A margin the factorisation records passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
At each of the 82 elimination steps of the multiple-shooting matrix over an interval of 12 at a step of 0.3: the relative gap between the largest and second-largest candidate pivot, the growth factor reached so far, and the first divided by the second, on a logarithmic axis. The growth climbs to 1.1·10⁴. Half of it has arrived by step 77, drawn as the vertical line. Before that the smallest ratio is 1.08·10⁻⁶ at step 75; after it, the last comparisons have margins as small as 9.08·10⁻⁵ and a ratio of 8.24·10⁻⁹ at step 81, but a reversal there can no longer remove the growth already made.
show: "margin-trace", T: 15
The arguments are the ones A margin the factorisation records passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
At each of the 102 elimination steps of the multiple-shooting matrix over an interval of 15 at a step of 0.3: the relative gap between the largest and second-largest candidate pivot, the growth factor reached so far, and the first divided by the second, on a logarithmic axis. The growth climbs to 1.34·10⁵. Half of it has arrived by step 97, drawn as the vertical line. Before that the smallest ratio is 8.9·10⁻⁸ at step 95; after it, the last comparisons have margins as small as 7.45·10⁻⁶ and a ratio of 5.56·10⁻¹¹ at step 101, but a reversal there can no longer remove the growth already made.
show: "margin-predict", noise: "nonzeros"
The arguments are the ones A margin the factorisation records passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
For the same seven shooting matrices, Gaussian noise added only to the nonzero entries, swept on a quarter-decade grid from 10⁻⁸, and the smallest level at which the median growth over fifteen draws is at most half the noise-free growth, divided by the smallest pivot margin recorded before half the growth had arrived, against the growth factor on a logarithmic axis. shooting, T = 6, h = 0.3: growth 75.2, margin 0.00564, halving noise 0.00316, share 0.56; shooting, T = 9, h = 0.3: growth 905, margin 0.00564, halving noise 0.00316, share 0.56; shooting, T = 12, h = 0.3: growth 11000, margin 0.00564, halving noise 0.00178, share 0.32; shooting, T = 15, h = 0.3: growth 1.3·10⁵, margin 0.00564, halving noise 0.00316, share 0.56; shooting, T = 12, h = 0.25: growth 11000, margin 0.0107, halving noise 0.00562, share 0.53; shooting, T = 12, h = 0.2: growth 11000, margin 0.0134, halving noise 0.00562, share 0.42; shooting, T = 9, h = 0.15: growth 905, margin 0.0137, halving noise 0.00562, share 0.41. The share stays between 0.32 and 0.56 while the growth changes by a factor of 1784.
show: "margin-trace", T: 6
The arguments are the ones A margin the factorisation records passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
At each of the 42 elimination steps of the multiple-shooting matrix over an interval of 6 at a step of 0.3: the relative gap between the largest and second-largest candidate pivot, the growth factor reached so far, and the first divided by the second, on a logarithmic axis. The growth climbs to 75.2. Half of it has arrived by step 37, drawn as the vertical line. Before that the smallest ratio is 1.61·10⁻⁴ at step 35; after it, the last comparisons have margins as small as 0.00564 and a ratio of 9.65·10⁻⁵ at step 40, but a reversal there can no longer remove the growth already made.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
246 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
rook and complete pivoting stay below 2 at T = 1.80 — checked 18 times
Wilkinson's matrix grows by 2ⁿ⁻¹ under partial pivoting and by 2 under the other two at n = 4 — checked 15 times
and inside the growth bound at T = 1.5 — checked 10 times
below the switch the growth is about e^(5T/6)/2, at h = 0.100 — checked 10 times
and no random matrix exceeds it at n = 4 — checked 8 times
and on the staircase more than complete pivoting at n = 6 — checked 8 times
partial pivoting compares exactly n(n+1)/2 entries at n = 6 — checked 8 times
Wilkinson's matrix attains the bound at n = 4 agree — checked 8 times
a third to two thirds of the margin, shooting, T = 6, h = 0.3 — checked 7 times
above the switch it is under 2, at h = 0.353 — checked 7 times
prediction within a factor of three, shooting, T = 6, h = 0.3 — checked 7 times
the rook compares a small multiple of that on a Gaussian matrix at n = 19 — checked 5 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 0.001 — checked 4 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 10⁻⁴ — checked 4 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 10⁻⁵ — checked 4 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 10⁻⁶ — checked 4 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 3·10⁻⁴ — checked 4 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 3·10⁻⁵ — checked 4 times
growth × σ ÷ margin lies between 0.4 and 1.5 at h = 0.1, σ = 3·10⁻⁶ — checked 4 times
and below one at h = 0.1 — checked 3 times
and no draw exceeds 2 under noise of 0.001 — checked 3 times
the product is flat in σ at h = 0.1 — checked 3 times
Wilkinson's median growth is 2 under noise of 0.001 — checked 3 times
dense noise has removed it there, h = 0.3 — checked 2 times
noise on the nonzeros keeps the growth on every draw at 10⁻³, h = 0.3 — checked 2 times
partial pivoting's growth is e^(5T/6)/2 at T = 13.20 — checked 2 times
a largest size the searches are affordable at
a largest size the three searches are affordable at
a matrix family this reading draws
a matrix the noise sweep is drawn for
a matrix with a nonzero entry
a noise level
a noise model this measurement defines
a number of shooting steps a dense factorisation is affordable at
a number of shooting steps the rows can be drawn for
a pivot rule this routine implements
a pivot search this routine knows
a reading of the growth factor this generator draws
a shooting step
a shooting step below the switch, where there is growth for noise to remove
a shooting step below the switch, where there is growth to cost
a shooting step the figure's interval range is drawn for
a shooting step the noise sweeps are drawn at
a shooting step the trigger sweep draws: 0.3, 0.2 or 0.15
a threshold between nothing and partial pivoting
a threshold the sweep measures: 1, 0.99, 0.9, 0.5 or 0.1
an error in E of two to five times the margin, large enough to move E₁₁ past one on some draws
an interval and step the margin cases include
an interval the step sweep is drawn for
and it is pivoting doing it — without the swaps the growth is far larger
and its growth times σ is between half and all of the margin at σ = 0.001
and its growth times σ is between half and all of the margin at σ = 10⁻⁴
and its growth times σ is between half and all of the margin at σ = 10⁻⁵
and no draw exceeds 2 under noise of 10⁻¹⁰
and no draw exceeds 2 under noise of 10⁻¹¹
and no draw exceeds 2 under noise of 10⁻¹²
and no draw exceeds 2 under noise of 10⁻¹³
and no draw exceeds 2 under noise of 10⁻¹⁴
and no draw exceeds 2 under noise of 10⁻⁴
and no draw exceeds 2 under noise of 10⁻⁵
and no draw exceeds 2 under noise of 10⁻⁶
and no draw exceeds 2 under noise of 10⁻⁷
and no draw exceeds 2 under noise of 10⁻⁸
and no draw exceeds 2 under noise of 10⁻⁹
and no draw exceeds 2 under noise of 3.2·10⁻¹⁰
and no draw exceeds 2 under noise of 3.2·10⁻¹¹
and no draw exceeds 2 under noise of 3.2·10⁻¹²
and no draw exceeds 2 under noise of 3.2·10⁻¹³
and no draw exceeds 2 under noise of 3.2·10⁻¹⁴
and no draw exceeds 2 under noise of 3.2·10⁻¹⁵
and no draw exceeds 2 under noise of 3.2·10⁻⁴
and no draw exceeds 2 under noise of 3.2·10⁻⁵
and no draw exceeds 2 under noise of 3.2·10⁻⁶
and no draw exceeds 2 under noise of 3.2·10⁻⁷
and no draw exceeds 2 under noise of 3.2·10⁻⁸
and no draw exceeds 2 under noise of 3.2·10⁻⁹
and the gap between bound and reality grows with n — 4.9 at n = 4, 1.1·10¹¹ at n = 40
and Wilkinson's record a margin of zero
complete pivoting keeps every row of U below twice the matrix's largest entry
dense noise, or noise on the nonzeros
enough matrices a size for a median
every shooting matrix grows ten times more than every random one
LU is for square matrices
matmul shapes agree
partial pivoting's backward error is more than a hundred times complete pivoting's at the longest interval
the badge sits clear of every line
the Gaussian size the map is drawn at — at 24 a random matrix can grow by less than two, and then no step comes before half its growth
the legend clears the axis label on their shared line
the rook's median growth sits between the other two at the largest size
the shooting matrix keeps its growth under noise of 10⁻⁸
the worst random growth at n = 40 is still single digits
Wilkinson's median growth is 2 under noise of 10⁻¹⁰
Wilkinson's median growth is 2 under noise of 10⁻¹¹
Wilkinson's median growth is 2 under noise of 10⁻¹²
Wilkinson's median growth is 2 under noise of 10⁻¹³
Wilkinson's median growth is 2 under noise of 10⁻¹⁴
Wilkinson's median growth is 2 under noise of 10⁻¹⁵
Wilkinson's median growth is 2 under noise of 10⁻⁴
Wilkinson's median growth is 2 under noise of 10⁻⁵
Wilkinson's median growth is 2 under noise of 10⁻⁶
Wilkinson's median growth is 2 under noise of 10⁻⁷
Wilkinson's median growth is 2 under noise of 10⁻⁸
Wilkinson's median growth is 2 under noise of 10⁻⁹
Wilkinson's median growth is 2 under noise of 3.2·10⁻¹⁰
Wilkinson's median growth is 2 under noise of 3.2·10⁻¹¹
Wilkinson's median growth is 2 under noise of 3.2·10⁻¹²
Wilkinson's median growth is 2 under noise of 3.2·10⁻¹³
Wilkinson's median growth is 2 under noise of 3.2·10⁻¹⁴
Wilkinson's median growth is 2 under noise of 3.2·10⁻¹⁵
Wilkinson's median growth is 2 under noise of 3.2·10⁻⁴
Wilkinson's median growth is 2 under noise of 3.2·10⁻⁵
Wilkinson's median growth is 2 under noise of 3.2·10⁻⁶
Wilkinson's median growth is 2 under noise of 3.2·10⁻⁷
Wilkinson's median growth is 2 under noise of 3.2·10⁻⁸
Wilkinson's median growth is 2 under noise of 3.2·10⁻⁹
Against the rule
It draws a decomposition and prints its residual. It calls
luFactor, luPivot,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A margin the factorisation records
Partial pivoting finds the second-largest candidate in every column it scans, and throws it away. Keep it, divide the gap by the growth reached at that step, and take the smallest over the steps before half the final growth has arrived. That one number, recorded by the factorisation that is already running, predicts the dense noise that halves the growth to within a factor of 0.92 to 2.4 on shooting matrices whose growth runs from 75 to 1.3·10⁵ and whose fragility spans three and a half decades — and on Wilkinson's matrix it is exactly zero.
Elimination, and the swapA pivot that searches one row and one column
Rook pivoting looks down a column for its largest entry, along that entry's row for a larger one, and back down that entry's column, until it finds an entry largest in both. On Gaussian matrices of size 64 it keeps the median growth factor at 2.53 against partial pivoting's 4.06 and complete pivoting's 1.88, and it compares 6,987 entries against 2,080 and 89,440. On Wilkinson's matrix it holds the growth at exactly 2 where partial pivoting reaches 9.2·10¹⁸. And on a matrix built to make it walk it compares 113,376 entries — more than complete pivoting.
Elimination, and the swapA threshold that holds the growth still
Partial pivoting's large growth on the shooting matrix rests on a margin of 5.6·10⁻³, and Wilkinson's rests on exact ties, which a perturbation at rounding breaks. A sparse code pivots with a threshold instead, taking the sparsest row among candidates within a factor τ of the largest. At every threshold from 1 to 0.1 both matrices grow by exactly as much as under partial pivoting. But the growth is now held by row counts, which no perturbation of the values can reverse: at τ = 0.1 it survives noise on the stored entries up to 0.56 on the shooting matrix, three hundred times more, and 0.18 on Wilkinson's, where partial pivoting's goes at 10⁻¹⁶. The margin that predicts it is the chosen candidate's height above the threshold line, and it needs no division by the growth.
Elimination, and the swapA trigger finer than the growth
Threshold pivoting cannot remove the shooting matrix's growth of 1.1·10⁴, because at τ = 1 it is partial pivoting. The proposal was a factorisation that notices growth on a step and searches as rook pivoting does after it, paying for the stricter search only where growth is made. But no step makes much: the largest one-step rise is exactly the growing mode's rate over one shooting interval, 1.284 at a step of 0.3, and 1.133 at 0.15. A trigger finer than that rate holds the growth at 2.00 for about two thirds of rook's extra search; one coarser never fires. And a trigger fine enough searches as rook on a quarter of an ordinary random matrix's steps.
Elimination, and the swapA worst case is as fragile as its margin
Wilkinson's matrix grows by 5.5·10¹¹ under partial pivoting, and adding Gaussian noise of 10⁻¹⁴ to every entry takes its median growth to exactly 2. The shooting matrix from a boundary-value problem grows by 1.1·10⁴, and noise ten million times larger leaves it untouched. The difference is what each worst case rests on. Wilkinson's rests on exact ties between candidate pivots, which any noise breaks. The shooting matrix's rests on a choice made by a margin of 5.6·10⁻³, and between 10⁻⁶ and 10⁻³ its median growth is that margin divided by the noise, times a constant between one half and four thirds.
Elimination, and the swapElimination is a sequence of choices
Gaussian elimination is taught as a procedure with no decisions in it. There is one decision at every step — which row to use — and every stability property the algorithm has comes from making it well.
Elimination, and the swapNoise the growth amplifies
The shooting matrix's growth of 1.1·10⁴ fell under noise as its pivot margin divided by the noise, and the explanation offered was noise reversing partial pivoting's choices. But noise of 10⁻⁵ is five hundred times smaller than that margin. Add the same noise only to the entries that are not zero and every draw keeps the whole growth up to 10⁻³. The dense noise was not reversing the comparisons by itself: it sat in the zeros, the elimination multiplied it by the growth already made, and a comparison flips when that product reaches about four tenths of the margin — at every noise level from 10⁻⁶ to 10⁻³.
Elimination, and the swapThe bound that is never attained
Partial pivoting's stability guarantee permits the entries to double at every step — a factor of 5.5·10¹¹ at n = 40. The measured growth on random matrices of that size is about three. The gap is eleven orders of magnitude, and the guarantee is still worth having.
Elimination, and the swapThe growth a boundary-value problem supplies
Large growth under partial pivoting is usually said to need a matrix built for it. A two-point boundary-value problem solved by multiple shooting supplies one without being asked: its growth factor is e^(5T/6)/2 to four figures — 1.1·10⁴ at an interval of 12, 1.3·10⁵ at 15 — on a matrix whose condition number never exceeds 8.3, while rook and complete pivoting keep it below 2. And it is the finer shooting grid that grows: below a step of 0.3397 the choice partial pivoting makes turns on one entry against one, and above it there is no growth at all.
Elimination, and the swapThe swap that is not optional
Run elimination without a row interchange on a matrix that needs one and nothing announces a failure. There is no division by zero, no warning, and an answer of the right shape. It is simply wrong, and how wrong depends on a number you did not look at.