Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Quasi definite matrix — where it appears

A symmetric matrix with a positive definite block, a negative definite block and anything in between them. It has a factorisation with a diagonal middle factor under every symmetric permutation, which lets the ordering be chosen for sparsity with no numerical veto at all.

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

-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 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.

Growth factorLDLᵀ factorisationSaddle-point systemsSymbolic factorisationBunch–KaufmanElimination treeFill-inInertiaIterative refinementMinimum degreeRegularisationSparse pivoting

All concepts