Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Arrowhead matrix — where it appears

A matrix with entries only on the diagonal and in one row and column, whose elimination costs nothing or everything depending on where that row sits. It is the smallest example of an ordering deciding everything: eliminate the spine last and the fill is nothing, eliminate it first and the factor is full.

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

the matrix43 entriestip eliminated first253 entriestip eliminated last43 entries‖A − LLᵀ‖/‖A‖, tip first1.4·10⁻¹⁶‖A − LLᵀ‖/‖A‖, tip last0dense factor is n(n+1)/2 = 253 · sparse factor is 2n − 1 = 43one row swapped to the endnothing numerical chose between them

Two ends of the same arrow

One matrix, one row moved from the front of the elimination order to the back, and the factor goes from completely dense to no fill at all. Both factorisations are exact to rounding, and nothing numerical chose between them.

sparsity · Fill 1234567891010⁻⁵⁵10⁻⁴⁹10⁻⁴³10⁻³⁷10⁻³¹10⁻²⁵10⁻¹⁹10⁻¹³10⁻⁷10⁻¹cyclesizethe residualrepairedthe reported boundwhat the stopping rule readsreported at the last cycle9.4·10⁻⁴¹the residual there5.7·10⁻⁵with the border recomputed3.8·10⁻¹⁴products, cheap and repaired9a bound with nothing under itand one product a cycle to fix it

Keeping the vectors, and losing the bound

Thick restarting keeps the Ritz vectors instead of filtering the starting vector — the same eigenvalues for a third of the products with A. Its residual bound reaches 9.4·10⁻⁴¹ while the residual it bounds sits at 5.7·10⁻⁵, and the eigenvalues are correct to 4.3·10⁻¹⁴ the whole time, so nothing reports it.

spectra · Lanczos

Named alongside it

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

CholeskyElimination orderFill-inFill-reducing orderingGaussian eliminationInvariant subspaceLanczosRayleigh quotientReorthogonalisationResidualResidual boundRestarting

All concepts