Null-space basis — the series
-
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.
-
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.
-
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.
-
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.