Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Null-space method — where it appears

A way of solving an equality-constrained problem by writing the unknown as a particular solution plus a combination of a basis for the constraint's null space. It leaves an unconstrained problem in fewer variables, whose conditioning depends on the basis chosen for that null space.

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

Also named here as range-space method — 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 systems -5-3-11350eigenvalueHZᵀHZK4 negative — Cholesky of H stops at row 30 negative — a minimum on the constraint(10, 4, 0) = In(ZᵀHZ) + (4, 4, 0)one factorisation, no Zpositive, LDLᵀ of K10negative, LDLᵀ of K4negative in H4negative in ZᵀHZ0the count follows the reduced Hessiannot the Hessian

A minimum the Hessian cannot see

A Hessian with four negative eigenvalues can sit at a constrained minimum, and a Cholesky of it stops at the third row. One symmetric indefinite factorisation of the saddle-point matrix settles the question anyway — ten positive pivots and four negative — without a basis for the null space ever being formed. The count is exact in the algebra and blind in floating point, in a band that grows like κ(A)²; the route through the null space is blind in one that grows like κ(A).

constraint · Saddle-point systems

Named alongside it

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

Condition numberConstrained minimisationRange-space methodReduced hessianSaddle-point systemsSchur complementBunch–KaufmanCertificateForward errorIndefinite matrixInertiaLDLᵀ factorisation

All concepts