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 3 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

Named alongside it

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

Nested dissectionFill-reducing orderingGreens functionKernel matrixNumerical rankOff-diagonal rankAnisotropyDiagonal dominanceElimination orderElimination treeFill-inFlop count

All concepts