Null space method — where it appears
Named by 10 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
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).
Spread resistances make the loops easy
Scaled to a unit diagonal, the loop equations on the least-resistance tree get easier as a network's resistances spread — from 120 to 5.44 over six decades — and stop depending on the grid's size, while the node equations of the same flow get harder, from 538 to 4.6·10⁴. The spread that ruins the range-space formulation rescues the null-space one, though the loops' density means the work saved is a factor of two, not the factor of nine the iteration counts suggest.
The tree the resistances choose
On a network every basic set is a spanning tree and every null-space basis is a set of loops with entries 0 and ±1, so no tree can make Z badly conditioned. The tree with the best-conditioned Z still gives loop equations 4.8 times worse than the tree of least resistance: the basis has to be chosen against the Hessian, and pivoting finds it only when it pivots on the resistances too.
A constraint the count stops seeing
Let one constraint drift towards being a combination of the others and the inertia of the saddle-point matrix keeps its promise only while σ²/|h| can be resolved — σ the constraint's smallest singular value, h the curvature along the direction it barely constrains. At h = −1 the count stops seeing the constraint at σ = 1.4·10⁻⁹, six decades before any rank test would drop it, and below that it reports a genuine minimum as a saddle on three to six draws in eight. No shift of H brings the constraint back: the correction loop shifts a problem that needed nothing by as much as 2,620. A perturbation of the constraint block does not bring it back either — it decides, at σ = √(|h|δ).
A loop that asks the null space why
An inertia-correction loop sees only an integer, and two different faults produce the same wrong one: curvature that needs a shift, and a constraint too weak for the count to see. One QR of the constraint matrix on a wrong count tells them apart — it shifts none of the 22 weak-constraint minima the ordinary loop shifted by up to 2,621 — and its reduced eigenvalue gives the shift a saddle needs in one step, twice the need exactly, where the schedule overshoots by up to 17,783 times. But at κ(A) = 10⁸ the loop still certifies 57 saddles of 152, because a false certificate is a count that read right, and a check made only on wrong counts never sees it. Asking every time leaves five, all shallower than 2·10⁻⁸.
A multiplier is a force
A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.
The scale that only moved a pivot
Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.
Long loops pay before the factor starts
The least-resistance spanning tree makes a network's loop equations well conditioned and its loops long, and the question left was what a direct solver pays for the length, and whether a tree reading the resistances only coarsely buys the conditioning back for less. Counted symbolically under minimum-degree ordering, the least tree's factor costs a median 1.2 to 2.0 times the breadth-first tree's on grids of 4 to 12 points a side, and the loop formulation goes from cheaper than the node equations at 4 × 4 to 3.8 times dearer at 12 × 12, for a conditioning two to three orders better. The price is paid in the loop matrix itself: on every network measured its factor fills in fewer entries than the breadth-first tree's. And no tree between them is a bargain. Kruskal on resistances rounded into bands pays nearly all the extra work until one band holds three quarters of the spread, and by then the conditioning has gone too.
The budget cannot finish the tree
The least-resistance spanning tree makes a network's loop equations well conditioned and its loops long, and the long loops cost a direct solver up to twice the breadth-first tree's factor work. A tree that refused any arc whose loop would run past a budget — 24 arcs, twice the breadth-first tree's longest — was predicted to keep the conditioning within twice the least tree's and save a third of the extra work. It keeps the conditioning and saves nothing. Every budget that binds leaves parts of the network it cannot join, the arcs it refused are needed to finish the tree, and they close loops as long as the least tree's. Half the least tree's loops are already as short as the property behind its conditioning allows; the slack is in the other half, and a greedy budget cannot reach it.
Named alongside it
The objects these essays reach for when they reach for this one.
Condition numberReduced hessianSaddle-point systemsSpanning-treeCertificateGraph laplacianInertiaLDLᵀ factorisationSchur complementConstrained minimisationEquality-constrained least squaresExact ground truth