The tree the resistances choose

The basis nobody chose on purpose found that a null-space method’s basis can be arbitrarily badly conditioned while the constraint it describes is fine, and it found the repair: choose the basic columns by a column-pivoted QR of the constraint matrix instead of taking the first ones listed. The pivoted basis had the orthonormal basis’s conditioning to within a factor of 1.25 and the naive basis’s sparsity exactly.

That repair reads the constraint and nothing else, and on the problem it was measured on nothing else mattered — the Hessian had a condition number of 100 and the naive basis had one of 10⁸. This essay takes a constraint on which the naive failure cannot happen at all, and a Hessian whose entries span four decades, and asks which basis is best when the basis is no longer the thing that can go wrong.

The constraint is conservation of flow on a network, and the answer is a spanning tree. It is not the tree that makes Z best conditioned, and it is not the tree a column-pivoted QR of the constraint picks.

Every tree is a basis, and every entry is a whole number #

The network is a square grid of 64 nodes joined by 112 arcs, each arc with a resistance. The constraint says that flow is conserved at every node: A is the incidence matrix, one column per arc, with +1 where the arc leaves a node and −1 where it enters, and one node — a corner — grounded, which removes its row and leaves 63 independent constraints on 112 unknowns. The null space has dimension 49, and a flow in it is a pattern of circulation that enters every node exactly as fast as it leaves.

A set of basic columns is a set of arcs, and those columns are independent exactly when the arcs contain no loop. A basic set of full size is therefore a spanning tree: 63 arcs reaching every node with no loop among them. The fundamental basis the tree gives has one column for each of the 49 arcs left off it, and each column is a loop — +1 on the off-tree arc, and ±1 along the unique path through the tree that closes it. Every entry of Z is 0, 1 or −1, and AZ = 0 holds in integers, for every tree.

That is the structural difference from a general constraint. There the fundamental basis carried the block −A_B⁻¹A_N, and a nearly singular basic block made its entries as large as twice the block’s condition number. On a network the basic block is a tree’s incidence matrix, its inverse holds only 0 and ±1, and no choice of tree can put a large entry into Z. The failure the pivoted rule was invented to prevent is absent.

The tree that conditions Z best #

Different trees still give different bases, and the difference in Z is a matter of how long the loops are. A column of Z is a loop, so its squared length is the number of arcs on the loop, and two columns overlap wherever their loops share tree arcs. Short loops that share little make columns that are short and nearly orthogonal; long loops through a common trunk make columns that are long and nearly parallel.

A breadth-first tree grown from the centre of the grid makes the loops as short as a tree on this grid allows: 310 nonzeros in Z, a mean loop of 6.3 arcs, the longest 10, and κ(Z) = 5.82. The same search grown from a corner makes every loop reach back towards that corner, and gives 490 nonzeros, loops up to 16 arcs and κ(Z) = 9.56. The tree a column-pivoted QR of the incidence matrix selects has loops up to 32 arcs and κ(Z) = 13.7. Among the six trees measured on this grid the centre breadth-first tree has the best-conditioned Z at every draw of resistances, since Z does not see them. The others follow their loop lengths only loosely: the longest loop decides a column’s length, and how many loops share a trunk decides how parallel the columns are, and the two need not agree.

Were the resistances all equal, that would be the end of it. With H a multiple of the identity, ZᵀHZ is a multiple of ZᵀZ and its condition number is exactly κ(Z)² — the square the normal equations take of any factor they are built from — and the tree with the shortest loops is the tree with the best reduced problem. Measured on the same grid with every resistance equal to one, the centre breadth-first tree gives κ(ZᵀHZ) = 33.9, the best of the six, and the column-pivoted QR of the incidence matrix gives 187.

Spread the resistances and the ranking turns over #

Now give each arc its own resistance, drawn at random over four decades, as a network of pipes or conductors of different sizes has. The constraint is unchanged, so every tree gives the same integer basis it gave before and the same κ(Z). What changes is H, and with it the reduced problem.

The centre breadth-first tree still has the best Z, at 5.82, and its loop equations now sit at 683. The tree of least total resistance — built by taking arcs cheapest first and skipping any that would close a loop — has a Z nearly twice as badly conditioned, κ(Z) = 11.2, and loop equations at 143, 4.8 times better. The column-pivoted QR of A, the repair recommended for a general constraint, gives 4,100. The tree of greatest resistance gives 4,040, and the corner breadth-first tree 3,530.

The standard bound κ(ZᵀHZ) ≤ κ(H)·κ(Z)² ranks those two trees the wrong way round. The factor κ(H) is common to both, so the bound’s verdict is decided by κ(Z)², and (11.2/5.82)² says the breadth-first tree should be better by a factor of 3.7. It is worse by a factor of 4.8. A bound that multiplies the Hessian’s condition number by the basis’s cannot see how the two are aligned, and here the alignment is the whole effect: the least-resistance tree has a worse basis that H happens to suit.

The effect is not an accident of one draw. On three further draws of resistances over the same four decades the centre breadth-first tree’s loop equations are worse than the least-resistance tree’s by factors of 5.8, 20.4 and 13.7, beside the 4.8 above. On none of the four does the breadth-first tree come within a factor of four, and on one it loses by more than twenty.

On that draw the least-resistance tree’s Z is a little better than on the first, 10.1 against 11.2, while its loop equations are worse, 358 against 143 — the two quantities move independently from one draw to the next, which is the same finding read across draws instead of across trees. Pivoting on the incidence matrix, which sees no draw at all, picks the same tree both times and lands at 4,100 on one and 1.77·10⁴ on the other.

Every loop of the least-resistance tree is closed by its heaviest arc #

The reason is a property of the tree that has nothing to do with conditioning and everything to do with how ZᵀHZ is assembled.

The diagonal entry of ZᵀHZ for a loop is the total resistance around it: its own arc plus every tree arc on the path back. The off-diagonal entry between two loops is the total resistance of the tree arcs they share. So a loop whose tree path carries a heavy arc has a diagonal entry dominated by that arc — and every other loop passing through the same arc has one dominated by it too, and all of those loops are coupled through it with an off-diagonal entry of nearly the same size. Rows that share one dominant term are nearly parallel, and nearly parallel rows are what an ill-conditioned matrix is. That is a mechanism rather than a measurement, and the measurement it predicts is the one below: whether each loop’s tree path carries an arc heavier than the loop’s own.

The tree built cheapest-first cannot put a heavy arc on a loop’s path unless that loop’s own arc is heavier still. That is the cycle property of a minimum spanning tree: every arc off the tree is the heaviest arc on the loop it closes, because had any tree arc on that loop been heavier, the cheapest-first construction would have taken the off-tree arc instead of it. So every diagonal entry of the least-resistance tree’s loop equations is led by an arc that belongs to that loop alone.

Measured loop by loop, the ratio of the heaviest resistance on the tree path to the loop’s own resistance is at most 0.975 on the least-resistance tree — below one on all 49 loops, as the cycle property requires — and falls to 0.00976. On the centre breadth-first tree it reaches 5,010 and exceeds one on 39 of the 49 loops. The breadth-first tree was grown without looking at the resistances, so it routes loops closed by light arcs through heavy tree arcs about as often as not, and each such loop is a row of ZᵀHZ led by a term it shares with its neighbours.

Pivoting works, on the matrix that includes the resistances #

The repair for a general constraint was a greedy rule: take as the next basic column the one with the largest component not yet spanned. Applied to A, the rule sees only the incidence pattern. Every column of an incidence matrix has the same length, $\sqrt{2}$, apart from the arcs at the grounded node, so the greedy choice is decided by projections among columns that all look alike, and it lands on a tree with loops up to 32 arcs long and κ(ZᵀHZ) = 4,100 — the worst of the six.

Apply the same rule to A scaled by the inverse square roots of the resistances, AH^(−1/2), and the column lengths become $\sqrt{2/r}$: the least resistant arc has the longest column and is taken first. That is the first step of the cheapest-first construction, and the rest of the greedy pass follows it closely. On this network the two rules produce the identical tree, and so the identical κ(ZᵀHZ) of 143.

Over a wider sample — grids of side 6, 8 and 10, resistances spread over two to six decades, five draws each, seventy-five networks — the pivoted QR of AH^(−1/2) produced the identical tree in 66. In the other nine it differed by at most three arcs, and its loop equations were within a factor of 1.54 of the least-resistance tree’s, while the centre breadth-first tree on those same nine networks was worse by factors from 1.2 to 31.8. The pivoted rule was never the wrong idea. It was applied to the wrong matrix: the reduced problem is ZᵀHZ, and a basis chosen by looking at A alone is chosen for ZᵀZ.

That is the general form of the finding, and it holds beyond networks. The quantity a null-space method factorises is the Hessian restricted to the null space, and a rule that selects the basis by examining the constraint optimises the conditioning of a matrix nobody factorises. Scaling the constraint by the Hessian’s inverse square root before pivoting is the smallest change that makes the rule look at the right thing, and when the Hessian is diagonal it costs nothing.

Where the ranking turns #

With every resistance equal the breadth-first tree wins, and with resistances over four decades it loses by 4.8. Between those there is a crossing, and sweeping the spread locates it.

At a spread of one the centre breadth-first tree’s loop equations are at 33.9 and the least-resistance tree’s at 91.5 — though with every resistance tied that second tree is simply the one the construction reaches by taking arcs in the order they are numbered, and it has none of the property the spread gives it. At a spread of ten the two are level, at 56.8 and 59.7. At a hundred the least-resistance tree is ahead, 48.2 against 123, and from there the gap widens with every decade, to 1,860 against 6,140 at a spread of a million. The greatest-resistance tree, which puts the heaviest arcs on the paths on purpose, climbs from 91.5 to 3.72·10⁴.

So the crossing is at about one decade of spread, which is less variation than almost any physical network has: two pipes in laminar flow whose diameters differ by a factor of two already differ in resistance by a factor of sixteen. For practical purposes a network whose arcs are not all alike is a network on which the tree should be chosen by resistance.

Two further readings of that sweep are left for a separate measurement. The node equations AH⁻¹Aᵀ — the range-space formulation of the same flow, which two ways to remove a constraint set beside the null-space one, and which on a network is a weighted graph Laplacian with its grounded row removed, one of the two Laplacians a graph carries — climb from 590 to 3.0·10⁵, worse than every tree at every spread. And even the least-resistance tree’s loop equations still grow, twenty-fold over six decades. Whether that growth is intrinsic or a matter of scale is a question about diagonal scaling, and the answer is not the one the unscaled numbers suggest.

What choosing the tree costs, and what it is not #

Building the least-resistance tree is a sort of the arcs by resistance and one pass with a union–find structure to skip arcs that would close a loop: O(n log n) for n arcs, against O(m²n) for a column-pivoted QR of an m × n constraint. On a network the pivoted rule on the scaled matrix is an expensive way of reaching nearly the same tree, and the cheap way reaches it exactly.

This is not the use of spanning trees in a preconditioner that is a tree, though the object is the same. There a tree’s Laplacian stands in for the whole graph’s inside an iteration on the node equations, its quality is measured by the stretch of the arcs off it, and on a uniform grid it made the conditioning worse by a factor of 1.85. Here the tree does not approximate anything: it selects a basis, the reduced problem is solved exactly, and what the tree decides is the condition number of that exact problem. The two uses reward different trees for different reasons, and the resistances enter this one through the cycle property rather than through stretch.

Nor does the choice of tree touch what the null-space method computes in exact arithmetic. Any two bases of one null space differ by an invertible matrix, and the spectrum of a constraint preconditioner is invariant under that change; every tree here gives the same flow to the last digit a rational solve would print. What the tree decides is only how many of those digits floating point keeps, which is the whole of the difference and none of the algebra.

It is also a sharper version of a pattern that keeps recurring in this field: a combinatorial choice made before any arithmetic decides a number the arithmetic then inherits, as the order that decides the memory does for fill. Eliminating a vertex is a graph operation, and the order in which vertices are eliminated fixes the fill before a single entry is computed; a spanning tree is a graph object too, and choosing it fixes the conditioning of the loop equations before a single loop is assembled. The difference is that the fill depends only on the graph, while the conditioning here depends on the graph and the weights together — which is exactly why a rule that reads only the graph gets it wrong.

Still open: whether the loops or the nodes are the easier system #

The sweep above leaves two numbers unexplained. The node equations are worse than every tree’s loop equations, by two to three orders at a spread of a million, and the least-resistance tree’s loop equations still grow with the spread. Both readings are of unscaled matrices, and a diagonal of resistances spread over six decades is exactly what an unscaled condition number over-reports.

Scaled to a unit diagonal — the cheapest preconditioner there is, and the one any iterative solver applies first — the two systems part company in a way the unscaled sweep does not hint at, and the grid’s size stops mattering to one of them. That is measured in spread resistances make the loops easy. Beyond it lie a Hessian that is not diagonal, where no tree reads the weights directly, and a sparse reduced problem whose fill depends on how many loops share each tree arc — a second thing the tree decides, and one that pulls the opposite way, since the least-resistance tree’s loops are longer.