Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Nested dissection — where it appears

A fill-reducing ordering that recursively splits a mesh by separators and numbers each separator last. It is asymptotically optimal on a grid, and the Schur complement it leaves on the largest separator is completely dense.

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

natural1739reverse Cuthill–McKee1354minimum degree1026nested dissection1413matrix: 408 entries · dense factor: 10440bandwidth 12 · 4.26× the matrixbandwidth 12 · 3.32× the matrixbandwidth 123 · 2.51× the matrixbandwidth 108 · 3.46× the matrixn = 144, five-point stencilevery ordering fills in; none avoids 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.

sparsity · ordering 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

Named alongside it

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

Fill-inFill-reducing orderingBandwidthElimination orderGaussian eliminationGreens functionHierarchical matrixKernel matrixMinimum degreeNumerical rankOff diagonal rankPermutation

All concepts