Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Incomplete cholesky — where it appears

A Cholesky factorisation that refuses to store any entry the matrix has as a zero, giving a cheap preconditioner and an inexact factor.

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

051015202530354010⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹iteration‖r‖ / ‖b‖plain CGIC(0) CGwhat the preconditioner didκ(A)48κ(L⁻¹AL⁻ᵀ)5.1‖A − LLᵀ‖/‖A‖0.0832D Laplacian, n = 100√κ ratio predicts 3.07×

Changing the condition number on purpose

Preconditioning is usually introduced as a trick that makes an iteration converge faster. It is not a trick. It is solving a different system with the same solution and a condition number chosen rather than inherited, and the new condition number is computable.

iterative · preconditioning 21018263442500102030405060708090100110120130140150160170180190200210220230240250260270280290300310320330340significand bitsiterationspreconditioner roundedarithmetic roundedno preconditionersame bits, different casualtyerror, 3-bit preconditioner8.8·10⁻¹³error, 3-bit arithmetic0.16‖A − LLᵀ‖/‖A‖ of the factor0.083a direction may be roundeda measurement may not

The part of a solver that may be rounded

A preconditioner computed and applied with a three-bit significand still returns thirteen correct digits — it costs seventeen extra iterations and nothing else. Round the working arithmetic instead and the step count barely moves while the answer loses exactly the digits the format dropped.

combination · mixed precision

Named alongside it

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

Conjugate gradientsPreconditioningCholeskyCondition numberFill-inForward errorHalf precisionJacobi iterationMixed precisionModel problemResidualSparsity

All concepts