Minimum degree — where it appears
Named by 14 essays across 3 fields — each of them below, with the objects they name alongside it.
The 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.
An ordering that does not wait for the numbers
A sparse factorisation's memory is decided by an ordering computed from the graph, and its stability by pivots computed from the values, and the two decisions fight. On one family of matrices they do not — the ordering can be chosen for fill alone, and the fill the symbolic phase predicts is the fill the factorisation produces — exactly, not as a bound.
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.
The 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.
Two 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.
Eliminating a vertex is a graph operation
Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw. The matrix that remains is still a graph — symmetric, zero row sums, nonpositive off the diagonal — and the ordering decides whether the fill is thirty-one edges or four hundred and sixty-five.
The 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.
The 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.
An 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.
Pieces 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.
A plan redrawn where it was refused
A symmetric indefinite factorisation planned once from the pattern loses its fill saving as small pivots are scattered through the diagonal — on an 8 × 8 grid it keeps 74 per cent of what re-reading the degrees at every step saves at one small pivot in twenty, and 20 per cent at three in ten. Redraw the plan for the remaining rows only when the pivoting criterion rejects the planned pivot, and it keeps 85 to 100 per cent at every share up to three in ten, reading a tenth to a quarter of the rows the step-by-step rule reads. Each redrawn plan heads off refusals that would have followed it: 3 re-plans where the fixed plan was refused 7 times, 9 where it was refused 17. Where the plan was never refused, redrawing costs nothing — and with half the diagonal small, no plan of any kind beats the natural order.
A small pivot with a small neighbour
A fill-reducing plan computed from the pattern loses its saving as small pivots are scattered through a symmetric indefinite matrix, and redrawing it where the pivoting test refuses it wins the saving back. Gather the same small pivots into one region and the prediction was that the fixed plan would do worse, because a whole region's ranking is wrong at once. It does better. On 8 × 8 and 10 × 10 grids the fixed plan is refused 0 to 6 times with the small pivots clustered, against 7 to 19 scattered, and at three in ten it saves 10 and 23 per cent of the natural order's factor where scattered it saved 3 and 9. The reason is in the Bunch–Kaufman test: a small pivot whose neighbour is also small cannot be passed over for that neighbour, so the test pairs the two into a block that keeps the planned row. Both plans still save something with half the diagonal small. And the step-by-step sparsest rule, best of all when the small pivots are scattered, falls behind the redrawn plan in a cluster.
A refusal has no fixed price
A symmetric indefinite factorisation planned once from the pattern is refused by its pivoting test where small diagonal entries sit, and the earlier essays read the refusal count as the plan's cost: scattered small pivots were refused 7 to 19 times and saved little, clustered ones 0 to 6 and saved much more. Put the small pivots along lines, each with two small neighbours, and the prediction of one refusal for every three small entries holds — between 0.25 and 0.42 on every share and grid. The rest of the reading does not. From a fifth of the diagonal up, the three layouts add within a factor of 1.6 of the same number of entries to the fixed plan's factor while their refusal counts differ by three to seven times. What moved the earlier savings was the baseline: the natural order's factor changes with the layout too, by 13 per cent at three in ten, and on the 10 × 10 grid the lines 'save' 19 per cent where the scatter saves 9 — with fixed-plan factors of 907 and 898 entries.
Long loops pay before the factor starts
The least-resistance spanning tree makes a network's loop equations well conditioned and its loops long, and the question left was what a direct solver pays for the length, and whether a tree reading the resistances only coarsely buys the conditioning back for less. Counted symbolically under minimum-degree ordering, the least tree's factor costs a median 1.2 to 2.0 times the breadth-first tree's on grids of 4 to 12 points a side, and the loop formulation goes from cheaper than the node equations at 4 × 4 to 3.8 times dearer at 12 × 12, for a conditioning two to three orders better. The price is paid in the loop matrix itself: on every network measured its factor fills in fewer entries than the breadth-first tree's. And no tree between them is a bargain. Kruskal on resistances rounded into bands pays nearly all the extra work until one band holds three quarters of the spread, and by then the conditioning has gone too.
Named alongside it
The objects these essays reach for when they reach for this one.
Fill-inSymbolic factorisationFill-reducing orderingElimination treeNested dissectionSparse pivotingSparsityBunch–KaufmanFlop countGrowth factorSeparatorSymmetric indefinite