Spread resistances make the loops easy

The tree the resistances choose settled which basis a null-space method should use on a network: the spanning tree of least total resistance, whose every loop is closed by the heaviest arc on it. It left two numbers standing that it did not explain. The node equations of the same flow — the range-space formulation, a weighted graph Laplacian — were worse than the loop equations on every tree at every spread of resistances measured. And even the least-resistance tree’s loop equations got worse as the resistances spread, twenty-fold over six decades.

Both of those readings were of unscaled matrices, and an unscaled condition number on a problem whose coefficients span six decades is mostly a report of the diagonal. No iterative solver runs on such a matrix as it stands. The first thing any of them does is divide each equation by its own diagonal entry, which costs one vector and is exact: a symmetric scaling to a unit diagonal is a change of variable in both directions, the kind the scaling that buys ten orders shows can remove what looked like intrinsic loss. So the question worth asking is what is left after that division.

What is left moves in opposite directions for the two formulations, and the direction is set by the spread of the resistances.

Scaled, the two systems move apart #

The network is the grid the tree was chosen on — 64 nodes, 112 arcs, one corner grounded — with the same seeded draw of resistances, stretched over a range that widens from nothing to six decades. At each spread three loop bases and the node equations are built and each is scaled to a unit diagonal. The figure at the head of the page is their condition numbers.

The loop equations on the least-resistance tree start at 120 with every resistance equal — where that tree is an arbitrary one, the order arcs happen to be numbered in — and fall, decade by decade, to 5.44 at a spread of a million. The loop equations on the centre breadth-first tree start better, at 37.9, and rise to 3,510. The greatest-resistance tree’s rise from 120 to 3.23·10⁴. The node equations rise from 538 to 4.6·10⁴. The least-resistance tree overtakes the breadth-first one between a spread of ten and a hundred, and from there every further decade of spread widens the gap.

Two things about that picture were not visible in the unscaled one. The first is that the loops on the right tree get easier, not merely less hard: the whole twenty-fold rise measured before scaling was diagonal spread, and at a spread of a million the unscaled 1,860 and the scaled 5.44 differ by a factor of 340 that division by the diagonal removes. The second is that scaling does nothing of the kind for the node equations, whose scaled condition number tracks their unscaled one within an order at every spread.

Unscaled, on a larger grid, every system gets worse with the spread and the loops only get worse more slowly: 148 to 2,000 for the least-resistance tree on a 10 × 10 grid against 1,040 to 1.31·10⁵ for the nodes. Read on its own that figure recommends the loops for being the lesser evil. The scaled figure says something different in kind — that one of the two formulations has a structure the spread helps — and the rest of this essay is about why that structure exists, where it stops, and what it is worth in work.

Every coupling between loops is lighter than both loops it couples #

The loop equations are assembled from the loops’ resistances. The diagonal entry for a loop c is the total resistance around it, which is at least the resistance w_c of the arc that closes it. The off-diagonal entry between loops c and d is a signed sum of the resistances of the tree arcs the two loops share. After scaling, the entry becomes that sum divided by the square root of the two diagonal entries.

The least-resistance tree adds one fact: every arc off it is the heaviest arc on its own loop. A tree arc t shared by loops c and d lies on both, so its resistance is at most w_c and at most w_d. Putting those together, the magnitude of each scaled coupling is at most

$$\sum_{t\ \text{shared}} \sqrt{\frac{w_t}{w_c}}\,\sqrt{\frac{w_t}{w_d}}$$

— a sum of products of ratios each no larger than one, and each of the kind measured loop by loop when the tree was chosen: a tree arc’s resistance against the arc that closes the loop. Spread the resistances and those ratios fall, because the arc that closes a loop and the arcs along its path are drawn independently over a wider range, and the closing arc has to be the heaviest of them.

Measured on the 8 × 8 grid, the median over all 49 loops of that path-to-own ratio is 0.426 at a spread of a hundred, 0.182 at ten thousand and 0.0775 at a million. The largest scaled coupling anywhere in the matrix falls with it, from 0.776 to 0.610 to 0.488. At a spread of a million the least-resistance tree’s ratios run from 0.963 down to 0.000964, while the breadth-first tree’s run up to 3.5·10⁵ — a loop closed by a light arc and routed through a tree arc three hundred thousand times heavier, which after scaling is a row nearly identical to every other row passing through that arc.

The argument has a limit that should be stated rather than hidden. It bounds each coupling; it does not bound the condition number. The largest off-diagonal row sum of the scaled matrix — the quantity a diagonal-dominance argument needs below one — is 8.31 at a spread of a hundred, 4.59 at ten thousand and 2.75 at a million. No row is diagonally dominant at any spread, so no Gershgorin disc certifies the 5.44 that is measured. The couplings get small and the matrix gets well conditioned together, and the second is a measurement rather than a consequence of the first.

A weak link is a small eigenvalue no diagonal can see #

The node equations fail for a reason of a different shape, and the same row-sum measurement shows it. Scaled to a unit diagonal, the node equations’ largest off-diagonal row sum is 1.41 at a spread of a hundred, 1.44 at ten thousand and 1.43 at a million — essentially constant — while their condition number climbs from 1,110 to 6,410 to 4.6·10⁴. Whatever is getting worse is not in any row.

It is in groups of rows. A weighted Laplacian’s diagonal entry at a node is the total conductance of the arcs meeting there, and dividing by it makes every node’s own neighbourhood look alike. What it cannot do is tell a node well joined to the rest of the network from a cluster of nodes joined to the rest only through high-resistance arcs. Such a cluster has a mode — the whole cluster raised in potential together — that costs almost no energy, and that mode is a small eigenvalue of the whole matrix sitting behind perfectly ordinary rows. Spread the resistances over more decades and the draw produces more clusters with weaker links. Eliminating a vertex joins its neighbours by conductances w_iw_j/Σw, and a weak link survives elimination as a weak link; grounding removes one exact null vector and none of the near ones.

That is also the duality the two formulations share. The arcs that make the node equations hard are the arcs of high resistance, because they are the weak links. The least-resistance tree leaves exactly those arcs off, where each becomes the arc that closes a loop — the leading term of its own diagonal entry. The same resistance that is a weak link for the nodes is a strong diagonal for the loops, and the spread that multiplies weak links multiplies strong diagonals.

The node equations’ difficulty has a familiar relative elsewhere in the graph field. A direction the smoother cannot see gave a grid Laplacian one strong direction and watched multigrid’s convergence factor rise from 0.20 a cycle to 0.96 with every entry of the matrix still unremarkable. Spread conductances are the same kind of difficulty without the regularity: instead of every arc in one direction being strong, arbitrary arcs are weak, and the modes they create lie along whatever clusters the draw happened to wall off. A smoother, a diagonal scaling and a row-by-row test all read one node’s neighbourhood at a time, and none of them can see a property that belongs to a group — which is why the remedy on the node side is always something that looks at the graph as a whole, a coarse space or a tree, and never a better local rule.

On the loop side no such remedy is needed, and the reason is the one the basis nobody chose on purpose found in general form: a null-space method’s reduced problem is only as good as the basis it is written in, and here the basis was chosen from the weights. Choosing the tree is the global step the node side lacks, paid once before the iteration starts instead of once per cycle inside it. Both Laplacians of a weighted graph, the combinatorial and the normalised, keep the weak links; only a change of formulation moves them onto the diagonal.

The size of the grid stops mattering #

A condition number that does not grow as the grid is refined is the property every discretisation wants and few formulations have. The scaled node equations with every resistance equal read 75.3, 247, 538 and 963 on grids of side 4, 6, 8 and 10, growing with the number of nodes as a Laplacian’s always does. The loop equations on the least-resistance tree, at a spread of a million, do not grow at all.

Across grids of side 4 to 10 the least-resistance tree’s scaled loop equations read 2, 1.6, 4.5, 6.13, 5.44, 3.97 and 5.01 — never above seven, with no trend. The breadth-first tree’s climb from 233 to 2.06·10⁴, and the node equations’ from 7,230 to 2.42·10⁴, with one draw at side 7 reaching 1.1·10⁶ — a draw that happened to wall a region of that grid off behind heavy arcs, which is the weak-link mechanism caught in a single instance, and which the loops on the same draw read at 6.13.

That flatness is a property of wide spread and not of loops. At a spread of a hundred the same sweep is not flat at all.

With resistances over two decades the least-resistance tree’s loop equations grow from 4.96 at side 4 to 66.6 at side 10, the breadth-first tree’s from 16.8 to 235, and the node equations’ from 247 to 1,560. The loops are still better by a factor of twenty or more, but they have a size dependence again. The bound above explains the difference: at a spread of a hundred a loop’s path arcs are typically within a factor of three of its closing arc, a long loop shares many of them with its neighbours, and a longer grid makes longer loops. Only when the closing arc is typically many times heavier than everything on its path does the length of the path stop counting.

Iterations, and what each one costs #

The practical reading of a condition number is an iteration count, and conjugate gradients with the diagonal as its preconditioner is the method whose count it predicts. Counted to a residual of 10⁻¹⁰ from the same seeded right-hand side — a count, so the comparison reads the same on any machine — the two formulations part company as the conditioning does.

On the 8 × 8 grid the least-resistance tree’s loop equations take 50 iterations with every resistance equal and 16 at a spread of a million; the node equations take 46 and 97. Across grid sizes at that spread, the loops take 7, 10, 14, 17, 16, 16 and 17 iterations on sides 4 to 10, and the node equations 17, 25, 40, 77, 97, 114 and 154. At side 10 that is a factor of nine.

An iteration is not a unit of work, and here the difference matters. The loop operator is applied as $Z^{\mathsf T}(H(Zv))$, which costs two passes over the nonzeros of Z and one over the arcs; the node operator costs one pass over the nonzeros of the Laplacian. And the least-resistance tree’s loops are long — that is the price named when the tree was chosen — so its Z has 48, 176, 426 and 928 nonzeros on sides 4, 6, 8 and 10, growing much faster than the Laplacian’s 59, 151, 283 and 455.

Counting iterations times nonzeros touched, at a spread of a million the loops cost 840, 5,768, 15,424 and 34,612 and the nodes 1,003, 6,040, 27,451 and 70,070. The null-space formulation is cheaper by factors of 1.19, 1.05, 1.78 and 2.02 — a real advantage that grows with the grid, and a much smaller one than the factor of nine in iterations. At a spread of a hundred the order reverses: the loops cost 1,080 to 87,548 and the nodes 885 to 39,130, so the node equations are cheaper by 1.2 to 2.2 times even though they take up to twice as many iterations. A code that forms the loop matrix explicitly rather than applying Z twice pays much the same, since the least-resistance tree’s ZᵀHZ at side 10 has 2,171 nonzeros against the Laplacian’s 455.

So the verdict has a threshold in it. Where the resistances span a few decades, the node equations are the sparser system and the cheaper one to iterate on, and the loops’ better conditioning does not pay for their density. Where the resistances span many — six here — the loops win in work by a factor that grows with the grid, and win in conditioning by orders.

What this says about the two formulations #

Two ways to remove a constraint compared the null-space and range-space methods on a constraint whose conditioning was the variable, and found the range-space method’s error growing with κ(A) while the null-space method’s stayed flat. On a network the constraint’s conditioning is fixed by the graph, and the variable is the Hessian. The finding has the same shape one level down: the range-space formulation inherits the difficulty of its coefficients through weak links no scaling reaches, and the null-space formulation, given the tree that suits those coefficients, turns the same difficulty into diagonal strength that scaling exposes.

It also places a preconditioner that is a tree. There a spanning tree’s Laplacian stood in for a uniform grid’s inside an iteration on the node equations, and made the conditioning worse by a factor of 1.85. A uniform grid is the case in which a tree has nothing to exploit, and it is the case here too: at a spread of one the least-resistance tree is an arbitrary tree, and its loop equations at 120 are worse than the breadth-first tree’s at 37.9. What trees exploit, used either way, is heterogeneity in the weights, and a measurement on equal weights is a measurement of the case in which a tree is merely a tree.

And the whole comparison is between two systems that are exact reformulations of one flow. Every flow computed here, by loops or nodes, on any tree, is the same flow in rational arithmetic; the scaling is exact; the tree is combinatorial. What differs is only how many digits and how many iterations floating point spends reaching it, which is the gap between identical algebra and different arithmetic that this field keeps measuring.

Still open: a Hessian no tree can read, and the fill the tree creates #

Everything here used a diagonal H — one resistance per arc, independent of every other arc. A Hessian with off-diagonal coupling, as mutual effects between arcs or a finite-element discretisation produce, has no one resistance per arc for a tree to sort by, and the cycle property that bounded every coupling has nothing to act on. Whether a tree chosen by the diagonal of such an H keeps any of the advantage, or whether the choice has to become a factorisation’s pivoting on ZᵀHZ itself, is the next measurement to make.

The other is fill. The least-resistance tree’s loops are long, which made its Z denser and cost it most of its iteration advantage in work. A direct method on the loop equations would pay for that density again in the fill of their factor, and a tree that balanced short loops against the cycle property — shorter paths among the arcs light enough to belong on a tree — might buy the conditioning at a fraction of the density. Whether such a tree exists on a grid, and how close it comes to both, is measurable with the same trees and loops and is not measured here.