Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sparse pivoting — where it appears

Choosing pivots in a sparse factorisation, where the choice decides both the accuracy and how many entries the factor will have. The two objectives are opposed, and every standard rule is a compromise between them with a threshold in it.

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

-1-0.75-0.5-0.25010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴log₁₀ σ — the barrier's reduction factorresidual after one reused stepconvergedthe pattern free, the factors notentries moved6off-diagonal0survived at σ = 0.996survived at σ = 0.106 steps0 stepsthe few entries that movedare the ones that dominate

What survives one step of the barrier

An interior-point method solves the same system dozens of times with the same pattern and different numbers, and exactly p entries change between one step and the next. The pattern is reusable for ever. The factorisation is reusable for none of them, and the threshold that says so is a reduction factor of about a per cent against schedules that use ten.

sequence · reuse 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.

Saddle-point systemsSymbolic factorisationActive setBarrier parameterCondition numberElimination treeFill-inGrowth factorInterior point methodIterative refinementLDLᵀ factorisationMinimum degree

All concepts