Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Static pivoting — where it appears

Fixing the pivot order before the numeric factorisation runs and perturbing any pivot that turns out to be too small, rather than searching for a better one. It buys a predictable sparsity pattern and pays with a perturbation whose size is discovered rather than chosen.

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

02468101210⁻¹⁸10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸member of the sequencebackward error of the solvefresh order · equilibrated kept orderringed: another pivot replaced hereone order, two sets of unitsfresh order, last member9.5·10⁻¹⁷kept order, last member4.8·10⁻⁹equilibrated, last member6.5·10⁻¹⁷pivots replaced, kept2pivots replaced, equilibrated0the perturbation floor √u1.1·10⁻⁸a reused pivot order is safe or notdepending on what the rows are measured in

The order that was right last time

A pivot order computed once and reused across a sequence saves the symbolic phase, and the price is that a pivot which was large may now be small. Replacing it with √u·‖A‖ costs eight orders of backward error and iterative refinement recovers a factor of 8.8 of them. Divide each row by its largest entry first and the same reuse costs nothing at all.

sparsity · sparse pivoting 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-inGrowth factorSymbolic factorisationBackward errorElimination treeEquilibrationIterative refinementLDLᵀ factorisationMinimum degreeQuasi definite matrixSaddle-point systemsSparse lu

All concepts