Fill against growth as the pivot threshold moves, on the 6×6 grid
At its defaults it draws fill against growth as the pivot threshold moves, on the 6×6 grid. Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
threshold-tradeoff is one function in lib/figures/sparselu.js —
sparse lu — where the fill argument and the stability argument disagree. 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.
Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
grid: 6
The arguments are the ones A threshold between fill and growth passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
grid: 4
The arguments are the ones A threshold between fill and growth passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
grid: 8
The arguments are the ones A threshold between fill and growth passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
grid: 5
The arguments are the ones A threshold between fill and growth passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
grid: 7
The arguments are the ones A threshold between fill and growth passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.
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.
59 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.
both factorisations reproduce the matrix at τ = 0.001 — checked 7 times
choosing the column too gives a smaller factor at τ = 0.001 — checked 7 times
PA = LU at τ = 0.001 — checked 7 times
on random sparse matrices choosing columns halves the fill at τ = 1 — checked 4 times
the constraint block has no diagonal entry at row 24 — checked 4 times
rows and columns with ties to the largest beats rows only at τ = 0.1 — checked 2 times
a Bunch–Kaufman constant between none and one
a constraint density this comparison draws
a grid between 4×4 and 8×8
a grid the scattered sweep draws
a grid this comparison is drawn on: 6, 8 or 10
a looser threshold gives less fill
a number of variables per constraint the family is built with
a static ordering ranks every row
a threshold between none and partial pivoting
a threshold from the sweep
a threshold the patterns are drawn at: 0.1 or 0.001
a threshold the size sweep is drawn at: 0.1 or 0.001
a tie-break this comparison draws
and at the loosest threshold far less growth
and more growth
and the fill falls with the column choice whichever way ties go
and the library default sits under both extremes
and the natural order's block arrives exactly when it meets a constraint row
but the growth still rises as the threshold falls
every accepted pivot passes the threshold
matmul shapes agree
so its first block comes later
the grid operator is symmetric before anything is done to it
the sparsest ordering holds fewer entries at every constant
the sparsest ordering wins at every constraint count
the sparsest rule defers the constraint rows and the natural one does not
the worst case does not order the two searches consistently
two columns hold the growth at one number below τ = 1
Against the rule
It draws a decomposition and prints its residual. It calls
sparseLU,
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 threshold between fill and growth
One number decides how small a pivot an elimination will accept. At 0.001 the factor holds 172 entries and the matrix grows by 1,330; at 1 it holds 260 and grows by 1.2. The libraries ship 0.1, and the measurement says why.
Sparsity, and what elimination costsAn order fixed before the numbers
On a saddle-point matrix whose constraint rows have no diagonal, taking the sparsest pivot at every step beat the natural order on fill and growth at once, and the reading was deferral: the constraint rows go last and have filled in by then. A code computes its ordering once, from the pattern. That static minimum-degree order holds fewer entries than re-reading the degrees on fourteen of sixteen settings, growth under two throughout — and it does not defer. It spreads the constraint rows through the elimination, each after two thirds of its own variables. Scatter small pivots through a grid instead and the plan is refused on up to 25 of 64 steps; its saving falls from 31 per cent to 3.
Sparsity, and what elimination costsHow few columns the search needs
A full row-and-column pivot search is quadratic in the active submatrix at every step, and no library performs one. Looking at a single sparsest column takes the median fill from 244 to 136 where the full search reaches 109 — four fifths of the benefit for a linear scan — and that share is 79, 83, 80, 89 and 92 per cent across five thresholds. The worst growth appears to favour the narrow search by a factor of six, and on the next draw it favours the wide one by two.
Sparsity, and what elimination costsStructure and stability stop being separable
The sparsest variable to eliminate on this matrix has a diagonal entry of 10⁻¹². Eliminating it produces the smaller factor, reproduces the matrix to 3.8·10⁻¹⁷ — better than pivoting does — and returns an answer wrong in the fifth digit.
Sparsity, and what elimination costsThe column that was never fixed
Every threshold-pivoting measurement so far chose the pivot row in a fixed column, and the routine's own description said that choosing the column as well would change the constants and not the argument. Measured, it changes the argument. On the 8×8 conflict grid the factor shrinks from 875 entries to 640 at the library default, and the growth factor that climbed to 2,209 as the threshold loosened stays at 2.54 at every threshold from 0.3 down to 0.001. What does most of the work is not the column but which of several equally cheap entries is taken — and on random sparse matrices, choosing the column without that makes the growth worse.
Sparsity, and what elimination costsThe freedom a symmetric factorisation does not have
Permuting rows and columns together leaves no column to choose, so the conflict between the sparsest pivot and the sound one should be worse rather than better. On a saddle-point matrix whose constraint rows have no diagonal entry at all, it is not there: taking the sparsest available pivot holds 70 entries against the natural order's 113 and a growth of 1.28 against 1.83 — better on both currencies at once, at every setting of the pivot test. The two-by-two blocks that make it legal cost 1.33 entries apiece.