Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Null space — where it appears

The set of vectors a matrix maps to zero. For a constrained problem it is the set of directions along which the constraint stays satisfied, so a basis for it turns a constrained minimisation into an unconstrained one of smaller size.

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

Also named here as reduced hessian — the same set of essays touches all of them, so they are one junction rather than several.

01234510⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹log₁₀ κ(A)condition number, and relative errorκ(S)κ(ZᵀHZ)range-space errornull-space erroragainst a BigInt answerκ(S) at κ(A) = 10⁵4·10¹⁰κ(ZᵀHZ), all stops21range-space forward error5.3·10⁻⁶null-space forward error5.8·10⁻¹²both are the same algebraand only one squares

Two ways to remove a constraint

A constrained system can be reduced by eliminating the multipliers or by eliminating the constrained directions. Both give the same answer in exact arithmetic and inherit different condition numbers — one of them squares the constraint's, and the other does not contain it at all.

constraint · saddle point system 012345610⁻³10⁻²10⁻¹110¹log₁₀ κ(A)eigenvalue of P⁻¹Kthe constraint is not in itnontrivial6at one8movement, six decades7.1·10⁻⁶drift at one6·10⁻⁵2m at onethe marks are a pencil that never saw Aand the lines are the preconditioned matrix

A preconditioner that need not know the constraint

Keep the constraint block exactly and replace the objective block by anything positive definite on the null space. The preconditioned matrix then has 2m eigenvalues at exactly one, and its remaining n − m are the generalised eigenvalues of a pencil in which the constraint does not appear. Sweep its condition number over six decades and they do not move in six digits.

constraint · block preconditioning κ(A) = 10⁶ throughout · κ(H) = 100 · the answer is the same answer for every basisorthonormal — κ(Z)1κ(ZᵀHZ)25.6relative error1.07·10⁻¹⁵first m basic — κ(Z)1.99·10⁸κ(ZᵀHZ)3.8·10¹⁶relative error0.0518pivoted basic — κ(Z)2.06κ(ZᵀHZ)31.9relative error6.71·10⁻¹⁶what the choice costsdensity, orthonormal1density, fundamental0.5κ(ZᵀHZ) ÷ κ(Z)², naive0.96error, pivoted choice6.7·10⁻¹⁶every one of them is a basisand one of them loses fourteen digits

The basis nobody chose on purpose

A method that eliminates a constraint has to pick a basis for its null space, and every basis is correct. Their condition numbers are eight orders apart, the reduced problem inherits the square, and the choice is usually made by a one-line rule nobody thought of as a numerical decision.

orthogonality · null space basis

Named alongside it

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

Condition numberReduced hessianSaddle-point systemsConstrained minimisationBlock preconditionerColumn pivotingConstraint preconditionerForward errorInertiaMatrix pencilMINRESNormal equations

All concepts