Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Minimum degree — where it appears

An ordering heuristic that eliminates next whichever remaining variable is coupled to the fewest others. It is computed from the sparsity pattern alone and is usually within a small factor of the best ordering known, which nobody can compute.

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 natural113 predicted · 113 countedminimum-degree63 predicted · 63 countedreverse Cuthill–McKee63 predicted · 63 countedthe shaded entries are fill: zeros of K that the factorisation makes nonzeroallocated before the numbersnatural113minimum-degree63reverse-cuthill-mckee63predicted minus counted0the symbolic phase decides the memoryand nothing later is allowed to argue

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.

sparsity · sparse pivoting

Named alongside it

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

Fill-inBandwidthElimination treeFill-reducing orderingGaussian eliminationGrowth factorLDLᵀ factorisationNested dissectionPermutationQuasi definite matrixSaddle-point systemsSparse pivoting

All concepts