Fill-in — where it appears
Named by 30 essays across 5 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.
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.
Two ends of the same arrow
One matrix, one row moved from the front of the elimination order to the back, and the factor goes from completely dense to no fill at all. Both factorisations are exact to rounding, and nothing numerical chose between them.
Changing the condition number on purpose
Preconditioning is usually introduced as a trick that makes an iteration converge faster. It is not a trick. It is solving a different system with the same solution and a condition number chosen rather than inherited, and the new condition number is computable.
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.
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.
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 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.
The fill that is not independent
Eliminate both halves of a grid and what is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged. Its off-diagonal block is 11 by 12 and six columns describe it to eight digits. Renumber the separator and the same block needs all eleven.
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.
The elimination the matrix does not need
The Kronecker form of AX + XB = C is dismissed with a hundred million entries and (2/3)n⁶ operations. Both price an elimination, and after the reduction both routes take, the matrix has exactly n³ nonzeros, none of them above the block diagonal, and nothing left to eliminate.
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.
A hierarchy with no grid behind it
On a graph Laplacian the algebraic V-cycle converges at 0.199 a cycle, its grid complexity is an unremarkable 3.05, and its operator complexity is 17.7 — one level of forty-one unknowns is entirely dense. The number people quote is the one that does not measure the work.
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 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.
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.
A tolerance is priced by the problem
Three tolerances from three fields sit on one pair of axes and agree to within a factor of 5.74. That factor is the ratio of the two curves that cannot move. Change the only problem in the comparison and the third curve's fitted slope swings from 0.188 to 0.040 while the printed spread does not shift by a digit.
The 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.
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.
The budget cannot finish the tree
The least-resistance spanning tree makes a network's loop equations well conditioned and its loops long, and the long loops cost a direct solver up to twice the breadth-first tree's factor work. A tree that refused any arc whose loop would run past a budget — 24 arcs, twice the breadth-first tree's longest — was predicted to keep the conditioning within twice the least tree's and save a third of the extra work. It keeps the conditioning and saves nothing. Every budget that binds leaves parts of the network it cannot join, the arcs it refused are needed to finish the tree, and they close loops as long as the least tree's. Half the least tree's loops are already as short as the property behind its conditioning allows; the slack is in the other half, and a greedy budget cannot reach it.
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.
A clique has no order
Ordering a dissection's pieces with their separator in view cut the critical path by a quarter, and the next proposal was to order the separator's own vertices by how much fill each carries in. On every separator the dissections here produce — the grid's rows, its level-set diagonals, and the level sets of three irregular graphs of 300 vertices — twenty-four shuffles of the separator's order give the same factor to the last entry. The reason is one line of graph theory: once the pieces are eliminated, a separator whose vertices all touch one connected piece is a clique, and a clique's order changes nothing. The order matters only on a separator that is not a clique, and the one built here to be that — two grid rows thick — loses to a separator of one row under every order tried. The separator's size is the decision; its order is not one.
The spare vertices lean one way
Every separator a dissection drew on grids and sparse geometric graphs was a clique once its pieces were eliminated, so the order inside it changed nothing; only a separator two rows thick, built by hand, was not. On geometric graphs at twice the density, level-set separators were predicted to come out several vertices thick where the level crosses a dense patch, with vertices touching only one side — failing the clique condition, making their order matter by more than five per cent, and paying more for trimming than for any order. On twenty-four graphs at three densities the spare vertices are there: up to thirteen in one separator. Not one separator fails the clique condition, because on every graph the spare vertices all touch the same piece, and two vertices that share a piece are joined through it. No shuffle of any separator moves the fill or the work by a single entry. Trimming the spare vertices into the piece they touch shortens the critical path by up to 48 per cent — and denser graphs have fewer of them, not more.
Named alongside it
The objects these essays reach for when they reach for this one.
Minimum degreeSymbolic factorisationSparsityFill-reducing orderingGrowth factorSparse pivotingGaussian eliminationNested dissectionPermutationElimination treeSeparatorThreshold pivoting