Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sparse LU — where it appears

Gaussian elimination on a matrix that is mostly zeros, storing only the nonzeros of the factors. Its pivots are chosen to keep both the fill and the growth small, and the two choices pull in different directions.

Named by 3 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 10⁻³10⁻²10⁻¹1110¹10²10³10⁴pivot threshold τgrowth factor · entries in L + U ÷ entries in Agrowth, rows onlygrowth, rows and columnsfill ratio, rows onlyfill ratio, rows and columns8×8 grid, 64 unknowns, 288 entriesτ = 0.001: rows only — 741 entries; growth2209τ = 0.001: rows and columns — 640 entries; growth2.5τ = 0.1: rows only — 875 entries; growth38τ = 0.1: rows and columns — 640 entries; growth2.5τ = 1: rows only — 986 entries; growth1.2τ = 1: rows and columns — 659 entries; growth1.2dashed: a fixed column · solid: the column chosen toothe same threshold rule in both

The column that was never fixed

Every threshold-pivoting measurement so far chose the pivot row in a fixed column, and the routine's own description said that choosing the column as well would change the constants and not the argument. Measured, it changes the argument. On the 8×8 conflict grid the factor shrinks from 875 entries to 640 at the library default, and the growth factor that climbed to 2,209 as the threshold loosened stays at 2.54 at every threshold from 0.3 down to 0.001. What does most of the work is not the column but which of several equally cheap entries is taken — and on random sparse matrices, choosing the column without that makes the growth worse.

sparsity · Sparse pivoting 80 matrices, τ = 0.1, ties to the largestno column search, median fill244one column136every column109share of the gain at one column0.804896144192240columns the search may look atmedian fill123468121624allno column search at allmedian fillmedian growthworst growth — see the captionthe fill is the quantity the width buysthe worst case is the draw

How few columns the search needs

A full row-and-column pivot search is quadratic in the active submatrix at every step, and no library performs one. Looking at a single sparsest column takes the median fill from 244 to 136 where the full search reaches 109 — four fifths of the benefit for a linear scan — and that share is 79, 83, 80, 89 and 92 per cent across five thresholds. The worst growth appears to favour the narrow search by a factor of six, and on the next draw it favours the wide one by two.

sparsity · Sparse pivoting

Named alongside it

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

Fill-inGrowth factorThreshold pivotingGaussian eliminationMarkowitz costPermutationSparse pivotingSymbolic factorisationBackward errorEquilibrationIterative refinementSparsity

All concepts