Nonzeros in the Cholesky factor of the 12×12 grid Laplacian, by ordering
At its defaults it draws nonzeros in the cholesky factor of the 12×12 grid laplacian, by ordering. A horizontal bar chart comparing the number of nonzero entries in the Cholesky factor under four elimination orderings, with reference marks for the matrix itself and for a dense factor.
ordering-bars is one function in lib/figures/sparse.js —
sparsity — fill counted two ways, and the ordering that decides the memory. 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.
A horizontal bar chart comparing the number of nonzero entries in the Cholesky factor under four elimination orderings, with reference marks for the matrix itself and for a dense factor.
show: "tree", measure: "work"
The arguments are the ones An ordering that buys processors, not time passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Against the side k of the grid Laplacian, on a logarithmic axis: the total work Σcⱼ² of the Cholesky factorisation, and the work along the elimination tree's most expensive path to its root, which is the time on unbounded processors. At k = 24 nested dissection does 158,003 against minimum degree's 103,481, and its critical path is 34,969 against 41,072. Over every size drawn the two critical paths are within 28 per cent of each other, in both directions.
show: "tree", measure: "speedup"
The arguments are the ones An ordering that buys processors, not time passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Total factorisation work divided by the work along the elimination tree's most expensive path, for the k×k grid Laplacian from k = 8 to 24. Under nested dissection it grows from 2.70 to 4.52; under minimum degree it stays between 2.07 and 2.63.
show: "tree", measure: "height"
The arguments are the ones An ordering that buys processors, not time passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The height of the elimination tree for the k×k grid Laplacian from k = 8 to 24, under the natural order, minimum degree and nested dissection. The natural order's tree is a path through every vertex of the k-by-k grid. Minimum degree's tree reaches 23, 36, 54, 64, 81 and nested dissection's 24, 36, 48, 60, 72 at the same sizes.
show: "tree", measure: "widest"
The arguments are the ones An ordering that buys processors, not time passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The largest column of the factor for the k×k grid Laplacian from k = 8 to 24, under the natural order, minimum degree and nested dissection. The natural order's largest column is k + 1. Minimum degree's reaches 11, 17, 24, 29, 38 and nested dissection's 11, 17, 23, 29, 35 at the same sizes.
grid: 16
The arguments are the ones An ordering that buys processors, not time passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A horizontal bar chart comparing the number of nonzero entries in the Cholesky factor under four elimination orderings, with reference marks for the matrix itself and for a dense factor.
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.
41 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.
nested dissection's speedup bound is the larger at k = 8 — checked 5 times
a dissection depth the recursion reaches
a graph small enough for every elimination order to be searched
a grid small enough for every elimination order to be searched
a grid the dial draws
a grid the study measures
a grid the study measures: 12, 16, 20 or 24
a grid the symbolic factorisation can afford at every depth
a grid the tie-break sample can afford
a reading of the elimination tree this figure draws
a size every elimination order can be searched at
a view of the orderings this figure draws
and minimum degree's worst arithmetic overshoot is larger than its worst fill overshoot
and one level of dissection is worse than none on both counts
and some ordering beats the natural one
and some tie-break of it is optimal on every one
and the other orderings' are not
enough graphs for a share and few enough for a 2ⁿ search each
every constrained vertex named once
every vertex numbered exactly once
minimum degree beats a dense factorisation
minimum degree is optimal on most graphs and not all
minimum degree still fills in
minimum degree's factor is the least there is on this grid
natural beats a dense factorisation
natural still fills in
nested dissection beats a dense factorisation
nested dissection still fills in
one order attains both minima on almost every graph
one to four levels of separators
reverse Cuthill–McKee beats a dense factorisation
reverse Cuthill–McKee still fills in
the least total work is at no dissection at all
the order the search recovers does the arithmetic the search counted
the order the search recovers has the factor the search counted
the tie-breaks spread less than the gap to nested dissection
while the shortest critical path is not at one level either
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
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.
An ordering that buys processors, not time
Nested dissection loses to minimum degree on fill and on total work at every grid either measurement could draw. Read along the elimination tree a parallel factorisation works on, it does not win back the time either: its critical path is within 28 per cent of minimum degree's at every size from 8 to 24 points a side, in both directions, and the tree heights and widest columns are nearly the same. What it wins is the ratio. Its total work over its critical path — the most a factorisation on unbounded processors can speed up by — grows from 2.7 to 4.5 while minimum degree's stays between 2.1 and 2.6.
Sparsity, and what elimination costsPieces ordered blind
One level of nested dissection followed by minimum degree lengthened the factorisation's critical path, and the blame moved from the separator to the halves: minimum degree's path through a 12 × 24 half was longer than through the whole 24 × 24 grid. A 12 × 24 grid on its own has a path of 12,913, a third of the square's. What made the half expensive is that it was ordered as if the separator were not there. Count the separator's vertices in every degree and number them last, and the depth-one path falls from 53,508 to 41,050 — minimum degree's own — while the pieces' own arithmetic does not change at all. At depth two the same ordering beats full dissection.
Sparsity, and what elimination costsThe depth that is worse than both ends
Nested dissection to a chosen depth and minimum degree below it is the ordering codes ship, and sweeping the depth was supposed to find a setting that keeps most of dissection's parallelism for most of minimum degree's work. It does not exist: total work rises with the depth at every grid size, and one depth — the first — is worse than both extremes on work and on the critical path at all four sizes measured. One bisection buys nothing because there is no recursion under it to amortise the separator.
Sparsity, and what elimination costsThe halves were the price
One level of nested dissection followed by minimum degree was worse than both no dissection and full dissection on a grid, and the explanation offered was the separator's dense block sitting on every path. That predicted a sign: a separator found from the graph, rather than read off the coordinates, should make the penalty larger. It makes it smaller at every size — 44,116 against 53,508 at 24×24 — and the separator is not where the difference is: both first separators have 24 vertices and cost exactly 4,900. What differs is the path through the halves. Minimum degree takes 48,608 through a rectangular half of the 24×24 grid, longer than its 41,072 through the whole grid, and 39,216 through a triangular one.
Sparsity, and what elimination costsThe least fill there is
Finding the elimination order with the least fill is NP-hard, and that is a statement about the hardest graph and the largest size. On a graph of twenty vertices every one of the 20! orders can be searched at once, through the million sets of vertices already eliminated, and the least fill is a number. On the 4×4, 4×5 and 3×7 grids minimum degree finds it exactly. On eighty random sparse graphs of eighteen vertices it finds it on 53 and misses by at most 7.6 per cent, and on every one of the eighty some breaking of its ties finds it.
Sparsity, and what elimination costsThe order decides the memory
Four elimination orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries. All four factorisations are exact, all four return the same answer, and the one with the better asymptotics is not the one that wins.
Sparsity, and what elimination costsTwo minima that are one minimum
The order that decides the memory found the operation count behaving like the square of the fill, which leaves room for an order with slightly more fill but a shorter heaviest column to do less arithmetic. Searched exactly over every elimination order on forty graphs, that order does not exist: one order attains both minima on thirty-nine of forty, and on the fortieth the least-fill order's arithmetic is 1.0099 times the least. Minimum degree attains both on the same thirty-three graphs and neither on the same seven.