Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Bunch–Kaufman — where it appears

The pivot rule that allows a symmetric factorisation to take two variables at once, so that a matrix with nothing on its diagonal can still be factorised. It keeps symmetry, exists for every nonsingular symmetric matrix, and bounds the growth by a constant involving the square root of seventeen.

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

D from PAPᵀ = LDLᵀ — the shaded pairs are 2×2 pivots10⁻⁶0.749······0.749·········1.2·10⁻⁶1.4······1.4·········2.1·10⁻⁶0.549······0.549·········3.6·10⁻⁶0.614······0.614·three rules, one matrix‖PAPᵀ − LDLᵀ‖, blocks5.8·10⁻¹⁷‖PAPᵀ − LDLᵀ‖, diagonal3.1·10⁻¹¹growth, blocks1.3growth, diagonal5·10⁵the zero block is what the problem saysand one rule does not need it to be nonzero

When symmetry is not enough

The matrix [[0, 1], [1, 0]] is symmetric, nonsingular and perfectly conditioned, and there is no diagonal entry to pivot on. Every factorisation restricted to symmetric interchanges and one-by-one pivots fails on it, at any depth of searching, because every entry it could search is zero. The repair is to take two variables at once.

elimination · cholesky -18-15-12-9-6-300log₁₀ ‖PKPᵀ − LDLᵀ‖ / ‖K‖share of orderingsbestworstexistence and stabilityfactorise1unregularised0.69worst growth6.4·10⁵growth × δ0.64the ordering is free to chooseand not free of consequence

The regularisation that legalises every order

Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.

constraint · quasi definite

Named alongside it

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

Growth factorLDLᵀ factorisationSaddle-point systemsCholeskyComplete pivotingConstrained minimisationIndefinite matrixInertiaIterative refinementPartial pivotingQuasi definite matrixRegularisation

All concepts