Long loops pay before the factor starts

Spread resistances make the loops easy found that on a resistor network the loop equations $Z^{\mathsf T}HZ$, built from the spanning tree of least total resistance, stay well conditioned however far the resistances spread, while the node equations of the same flow get worse. The tree that does it, the tree the resistances choose, follows the light arcs wherever they go, and its loops are long. In an iterative solve that cost most of the conditioning’s advantage, because each product with a long loop touches many arcs.

The essay left the direct solver’s side open in two sentences. “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.”

Both are measured here. The first sentence is right about the price and wrong about where it is paid. The second is wrong.

The work of a factor, counted without numbers #

The networks are the earlier essays’: a square grid of $k \times k$ nodes, an arc between neighbours, one node grounded, and a resistance on each arc drawn log-uniformly over a stated number of decades. A spanning tree picks a fundamental loop for every arc off it, and the loop equations are a symmetric positive definite matrix with one row per loop, nonzero wherever two loops share an arc.

A direct solver factors that matrix by Cholesky. How much the factor costs is decided by its pattern of nonzeros and the order the unknowns are eliminated in, and not by the numbers in it, so it can be counted exactly without computing anything. The ordering used is minimum degree, the greedy rule the least fill there is measured against the true optimum on small graphs: eliminate the unknown with the fewest neighbours, connect its neighbours to each other, repeat. Two counts come out. The entries of the factor, and the work, the sum over pivots of the square of the pivot’s column count, which is what the dense column updates cost to leading order. Conditioning is measured on the loop matrix scaled to a unit diagonal, which is what the earlier essays used and what a diagonal preconditioner sees.

The figure at the top of the page is the result on a 10 × 10 grid with resistances over four decades, median over five draws. The breadth-first tree’s loop equations factor with 8,547 units of work and a conditioning of 2,480. The least tree’s need 16,913, twice as much, at a conditioning of 12.5, two hundred times better. The node equations, the range-space formulation of the same flow, need 5,111 at a conditioning of 6,960. And the trees between them, which the rest of this essay is about, do not sit on a line between the two ends: they stay at the dear end of the work axis while the conditioning holds, and come back toward cheap work only after the conditioning has gone.

Where the least tree’s work comes from #

The earlier essay expected the long loops to be paid for in fill, the entries elimination creates where the matrix had zeros.

On this 8 × 8 network the breadth-first tree’s loop matrix has 613 nonzeros and its factor adds 45 entries of fill to each triangle. The least tree’s has 931 nonzeros and adds 15. Its factor still costs twice the work, 6,161 against 3,124, but the reason is not fill: the matrix it starts from is half as dense again, and elimination makes less of it worse. The same holds on every network measured — grids of 4, 6, 8, 10 and 12 points a side, five draws each. On all twenty-five the least tree’s loop matrix is denser, by a factor of 1.12 to 1.89, and its factor fills in fewer entries than the breadth-first tree’s: 0 to 121 against 3 to 175.

The reason is in the loops themselves. A long loop shares arcs with many other loops, and every pair of loops that share an arc is a nonzero of $Z^{\mathsf T}HZ$ before any elimination happens. Elimination then mostly connects loops that were connected already. The breadth-first tree’s loops are short and local, so the loop matrix is sparse and grid-like, and eliminating it fills the gaps a grid always leaves, the way the node equations’ Laplacian does. The least tree’s loops pay first, in their own overlaps.

The lengths show where the overlaps come from. On the 10 × 10 network the breadth-first tree’s 81 loops have a mean of 7.31 arcs and none longer than 12. The least tree’s have a median of 6 — shorter than breadth-first’s 8 — and a mean of 11.46, because a minority are very long: the longest runs to 42 arcs, on a grid where the shortest path between opposite corners is 18 arcs. Most loops of the least tree close a heavy arc across a short gap. A few close an arc the tree reaches only by wandering, and those few loops overlap with dozens of others. The work of the factor is set by them. That is also why the count can be made before any factorisation: the loop matrix’s nonzeros are pairs of loops sharing an arc, readable off the loops, and an ordering that does not wait for the numbers is the general case of deciding a factor’s cost from a pattern alone.

The loops lose ground as the grid grows #

Over the breadth-first tree the least tree’s factor costs a median 1.22, 1.56, 1.44, 1.98 and 1.78 times as much on grids of 4 to 12 points a side, with a worst case of 3.08 at 10 × 10. That ratio does not run away. The ratio to the node equations does. At 4 × 4 the loop formulation is the cheaper one, 0.75 times the node equations’ work, because it has fewer unknowns: 9 loops against 15 nodes. At 12 × 12 the loop formulation has 121 unknowns against the node equations’ 143, still fewer, and costs 3.80 times as much, from 3.21 to 4.86 over the five draws. A grid’s node equations are a planar Laplacian, the case orderings were designed for, and their fill grows slowly. The loop matrix of a tree that follows the resistances is not planar in any useful sense, since its long loops couple distant parts of the grid, and its density grows with the longest loops.

The conditioning the work buys is large and holds with size. On the 10 × 10 grid the least tree’s loop equations are a median 198 times better conditioned than the breadth-first tree’s and 555 times better than the node equations. For a direct solve the conditioning sets how many digits the answer loses, through $\kappa u$; on these sizes and in double precision every formulation keeps eleven or more, so the trade matters for a reduced-precision factorisation or for a network whose resistances spread further than four decades. Two ways to remove a constraint drew that line in general: the null-space and range-space routes give one answer in exact arithmetic and lose different digits in floating point.

A tree that reads the resistances coarsely #

The earlier essay’s second sentence proposed a middle tree: one that follows the light arcs, which buys the conditioning, without following them so faithfully that its loops wander. The natural family is Kruskal’s algorithm on rounded resistances. Round every resistance’s logarithm down to a band of $\beta$ decades, take arcs band by band from the lightest, and within a band take them in breadth-first order from the centre. A band of zero width is the least tree. A band wide enough to hold every resistance is a breadth-first tree. In between, the tree respects the resistances only to the precision of a band.

With bands of a decade the tree on this network has loops of a mean 9.60 arcs and a longest of 34, a factor costing 17,628 units of work, and a conditioning of 45.2. The least tree had 11.46, 42, 18,896 and 14.8. So a decade’s rounding shortens the loops a little, saves 7 per cent of the work and costs a factor of three in the conditioning. On the dial the pattern holds across the family: as the bands widen the loops shorten slowly, the work barely moves, and the conditioning goes. Only at one band does the tree become breadth-first, with loops of 7.31 arcs, a longest of 12, work of 8,547 and a conditioning of 1,700.

What a band does to the cycle property #

The conditioning of the least tree’s loop equations came, in the earlier essays, from one property: every arc on a loop’s tree path is lighter than the loop’s own off-tree arc. That bounds how strongly two loops are coupled relative to their own diagonals, and the unit-diagonal scaling turns the bound into a condition number that does not grow with the spread. The measure of it is the heaviest resistance on a loop’s tree path over the resistance of its own arc, maximised over the loops; it is below one for the least tree by construction.

A band of $\beta$ decades relaxes it by at most a factor of $10^\beta$, since inside a band the tree takes arcs in breadth-first order and may put an arc on a path that is heavier than the arc closing the loop, by up to the band’s width. Measured on the 10 × 10 network at four decades, median over five draws, the worst ratio is 0.97 for the least tree, 1.23 with bands of a quarter decade, 2.87 at half a decade, 8.87 at a decade, 64.5 at two and 544 at three, each under its bound of $10^\beta$ and within a factor of two of it. The breadth-first tree, which ignores the resistances, reaches 5,480. So a band does exactly what it promises to the cycle property, a violation no worse than its width, and the conditioning follows the violation: the median conditioning over the least tree’s is 1.00, 1.38, 2.97, 18.9 and 11.1 at the five band widths in the same order. What a band does not do is shorten the loops, because shortening them needs the tree to stop following light arcs, and inside each band it still follows them, only in a coarser order.

The work is paid as soon as the resistances choose #

Because the resistances are drawn log-uniformly, two bandings with the same width as a fraction of the spread give exactly the same tree. So the family has one parameter that matters: how much of the spread one band covers.

Measured as a share of the least tree’s extra work, a banded tree pays a median 1.00 or more of it with bands up to a sixth of the spread, 0.82 to 0.88 at a quarter to a third, and 0.66 at half. A banded tree can pay more than the least tree, up to 2.28 times its extra work on one draw, because rounding replaces the least tree’s ordering with an arbitrary one inside each band and the loops that result are no shorter. The share falls to nothing only when one band holds three quarters of the spread or all of it, 0.04 and 0.00. A tree that lets the resistances choose at all pays nearly the whole price of letting them choose exactly.

The conditioning is lost on the opposite schedule. With bands an eighth of the spread wide or narrower it is within 1.53 times the least tree’s on every spread measured. At a quarter it is 1.22 and 2.97 times on two and four decades, and 2.13 at a sixth on six; at half, 1.58, 18.9 and 276 times; with one band, the breadth-first tree, 5.9, 198 and 7,240 times. The wider the spread, the faster coarse bands lose it, because each band then mixes resistances further apart and the cycle property that bounded every coupling, found by the tree the resistances choose, fails by more.

Put the two figures together and the middle tree is not there. The measurement asks, for every band width at every spread, whether the median conditioning stays within three times the least tree’s while the work falls below half of the extra. None does. The work stays near its full price until the bands are wide enough to cost the conditioning a factor of ten or more, and the frontier at the top of the page is that fact as a curve: it runs along the top of the work axis while the conditioning is still good and drops only when the conditioning has gone.

What a solver can take from this #

Long loops cost the factor twice the work, not more, at these sizes: a median 1.2 to 2.0 times the breadth-first tree’s, and the ratio does not grow with the grid. A preconditioner that is a tree priced a tree’s loops by their stretch for an iterative method; for a direct one the measure is the loop matrix’s density, which the stretch drives.

The cost is in the matrix, not the elimination, so it is visible before any factorisation: the loop matrix’s nonzeros, which are counted from the loops, predict the least tree’s extra work where the fill does not.

The node equations factor more cheaply from 6 × 6 upwards and the gap widens, to 3.8 times at 12 × 12. The loop formulation’s case on a direct solver is its conditioning, two to three orders better here, and nothing else.

There is no middle tree in this family. Reading the resistances coarsely keeps the cost and loses the benefit. The basis nobody chose on purpose began this line with the observation that the choice of basis is usually made by a one-line rule nobody thought of as numerical; on a network the rule that matters most for a direct solver is the one that decides whether the resistances choose the tree at all.

What five draws on grids do not show #

Planar grids only, with resistances drawn independently and log-uniformly; a network with correlated resistances, light corridors and heavy regions, would give the least tree long loops along the corridors and might change both the density and how fast banding loses the conditioning. One ordering, minimum degree, applied to each matrix separately; nested dissection would cut the node equations’ work further on a grid and would find less to cut in a loop matrix whose long loops cross every separator. The work is a symbolic count of dense column updates, not a time, and a supernodal code would charge the denser loop matrix less per entry. Five draws give medians whose ranges are wide, from 1.05 to 1.97 for the least tree’s work over breadth-first’s on the 8 × 8 grid, and every comparison above is a median with its range beside it.

Still open: a tree that limits its loops, and a separator the loops respect #

A tree with a length budget. The family here rounds the resistances and leaves the loop lengths alone, and the long loops were the whole cost. A tree built by Kruskal on exact resistances but refusing any arc whose fundamental loop would exceed a stated length, falling back to the next arc, attacks the cost directly. The prediction with a sign is that on the 10 × 10 grid at four decades a budget of twice the breadth-first tree’s longest loop, 24 arcs, keeps the median conditioning within twice the least tree’s and cuts at least a third of its extra work — that a length budget is a middle tree where a resistance band is not.

An ordering that knows the loops. Minimum degree sees only the loop matrix’s pattern. Ordering the loops by where on the grid their off-tree arc sits, so that a nested dissection of the grid induces one of the loops, would let the long loops be eliminated last. The prediction is that it reduces the least tree’s factor work on the 12 × 12 grid by at least a fifth below minimum degree’s, and leaves the breadth-first tree’s within a tenth of it, since short loops already follow the grid.