Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Elimination tree — where it appears

The tree recording, for each column of a sparse Cholesky factor, the first row below the diagonal that holds a nonzero. It fixes which columns must be eliminated before which, so its height bounds how few parallel steps the factorisation can take.

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

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

Minimum degreeSymbolic factorisationFill-inFill-reducing orderingFlop countGrowth factorLDLᵀ factorisationNested dissectionQuasi-definite matrixSaddle-point systemsSeparatorSparse pivoting

All concepts