Symbolic factorisation — where it appears
Named by 19 essays across 4 fields — each of them below, with the objects they name alongside it.
The factor is not sparse
A sparse matrix has a factor that is not sparse, and the gap between them is the entire reason iterative methods exist. The entries elimination creates can be counted before any arithmetic runs, from the graph alone.
Structure 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.
Which pairs are allowed to be small
A hierarchical representation is a partition of the matrix into blocks, and the rule that produces it reads four numbers per pair of index clusters and not one entry of the matrix. On a 256-square it yields 112 blocks, 66 of them stored as two thin factors, none of rank above five.
What the symbolic phase can only bound
Without pivoting, the fill can be computed from the graph and the count is exact — 233 predicted, 233 measured. With pivoting it is 233 predicted and 242 measured, and what survives is a bound that is right at every threshold and loose by 1.7 times at the largest grid drawn.
The regularisation that legalises every order
Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.
The order that was right last time
A pivot order computed once and reused across a sequence saves the symbolic phase, and the price is that a pivot which was large may now be small. Replacing it with √u·‖A‖ costs eight orders of backward error and iterative refinement recovers a factor of 8.8 of them. Divide each row by its largest entry first and the same reuse costs nothing at all.
What survives one step of the barrier
An interior-point method solves the same system dozens of times with the same pattern and different numbers, and exactly p entries change between one step and the next. The pattern is reusable for ever. The factorisation is reusable for none of them, and the threshold that says so is a reduction factor of about a per cent against schedules that use ten.
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.
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.
How 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.
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.
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.
The baseline was the interchanges
Small pivots along grid rows gave a fixed fill-reducing plan twice the saving over the natural order that scattered ones did, for a factor of the same size, and the reading was that the natural order did badly on rows. Turning the lines to run along columns was predicted to bring the natural order below 1,000 entries, leave the plan within 3 per cent of 907, and drop the saving to the scatter's. It misses on all three: 1,008, 977 and 3.1 per cent. What the natural order paid for on rows was its own interchanges. Offered by position, as a dense code offers it, every Bunch–Kaufman interchange moves a row out of sequence, and on rows that costs 125 entries at three in ten and 191 at half — the most of any layout at every share. Kept to the grid's index, the natural order barely notices the layout, and the row lines' saving halves to 9.0 per cent.
Named alongside it
The objects these essays reach for when they reach for this one.
Fill-inMinimum degreeFill-reducing orderingGrowth factorSparse pivotingSparsityBunch–KaufmanElimination treeSaddle-point systemsSymmetric indefiniteElimination graphFlop count