Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Factorisation — where it appears

Writing a matrix as a product of matrices with structure, which is what makes a solve cheap and what a residual is printed to check.

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

024681012141610⁻¹1index kλthe transformthe eigensolverC = F* Λ F is a factorisationworst relative disagreement2.6·10⁻¹⁵‖Cx − b‖/‖b‖ from the transform solve4.7·10⁻¹⁶imaginary part of a real spectrum1.2·10⁻¹⁶n = 16, and the whole matrix is 16 numberseigenvectors known in advance

The matrix that is one row

A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly. An eigensolver spends a sweep of Jacobi rotations over 256 entries arriving at the same answer, and agrees to 1.2·10⁻¹⁵.

structure · circulant 10¹10³10⁵10⁷10⁹10¹¹110¹10²10³10⁴condition number of the matrixgrowth factorbound 2^11partial pivotingCholeskyno pivot to gain fromCholesky growth, every κ1Cholesky interchanges0partial pivoting, worst9the bound, 2^112048both eliminations reach the same growthand only one of them had to swap to get there

A factorisation with nothing to pivot for

Cholesky's growth factor is not bounded by one. It is equal to one, at every size and every condition number, and the two-line reason is why the algorithm needs no pivoting at all — not "usually gets away without it". Its only failure is the square root of a non-positive number, which is exactly the test for definiteness, and in floating point that test moves with the precision.

elimination · cholesky

Named alongside it

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

CholeskyCirculant matrixCondition numberDiscrete fourier transformEigenvaluesFast fourier transformGaussian eliminationGrowth factorLDLᵀ factorisationMatrix structurePartial pivotingPositive definite

All concepts