Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Separator — where it appears

A set of unknowns whose removal splits a sparse matrix's graph into two halves that share no edge. Nested dissection numbers it last, so eliminating the halves first leaves a dense Schur complement on the separator alone, and its length is what the cost of the factorisation is counted in.

Named by 7 essays across one field — each of them below, with the objects they name alongside it.

0481216202402468101214unknowns on the separatorcolumns above 10⁻⁸the same matrix, renumberedin the separator's own orderthe ordering the geometry hands overseparator 73separator 236renumbered, largest11the block, largest11share of the square stored0.52the fill is totaland it is not independent

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.

sparsity · Fill 02468101210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹singular value, in orderσ ⁄ σ₁eight digitsrenumberedin the separator's orderthe same cliff, from the other endσ₂ ⁄ σ₁0.062σ₄ ⁄ σ₁1.3·10⁻⁴σ₆ ⁄ σ₁1.5·10⁻⁸renumbered σ₄ ⁄ σ₁0.63rank at 10⁻⁸6the same entriesin two orders

The cliff behind the count

The fill's rank is an integer between three and six across every separator two dense half-eliminations can afford, and this field has already recorded that a handful of such integers cannot carry a law. The singular values underneath are real numbers. They say the cliff's first step is 23.0 at a separator of eleven, 19.1 at fifteen and 16.2 at twenty-three — and that a control with no differential operator behind it gives 14,672.

sparsity · Fill 6101418222610³10⁴10⁵grid side karithmeticND, totalMD, totalMD, critical pathND, critical pathdashed: the time on unbounded processorsthe same time, bought with more work

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 · Ordering total operationswork, no dissection10⁵work, full dissection1.5·10⁵work, one level1.3·10⁵on unbounded processorscritical path, no dissection4.1·10⁴least, at depth 43.4·10⁴critical path, one level5.4·10⁴10⁵switching depthoperations01234568total operationscritical pathdepth 0 is minimum degree, depth 8 is nested dissectiondepth 1 is worse than both

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.

sparsity · Ordering rows and columns, from the coordinateslevel structures, from the graph aloneseparator, level 1separator, level 2separator, level 3same vertex count in the first cutdifferent pieces under it

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.

sparsity · Ordering critical pathdepth one, pieces alone5.4·10⁴depth one, separator counted4.1·10⁴minimum degree, whole grid4.1·10⁴01000020000300004000050000dissection depthcritical path, Σ c² along the heaviest chain12348minimum degreepieces ordered aloneseparator countedgrey line: full dissectionthe penalty was the blindness

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.

sparsity · Ordering longest ÷ shortesttwo rows, 12²1.5two rows, 24²1.311.11.21.31.41.5longest ÷ shortest critical path12²16²20²24²12²16²20²24²g1g2g312²16²20²24²grid, one rowgrid, level setgeometric graphgrid, two rowsdashed: every shuffle gives the same factorfree unless the separator is thick

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.

sparsity · Ordering

Named alongside it

The objects these essays reach for when they reach for this one.

Nested dissectionFill-reducing orderingElimination treeFill-inMinimum degreeCritical pathFlop countSymbolic factorisationGreens functionKernel matrixNumerical rankOff-diagonal rank

All concepts