A plan redrawn where it was refused

An order fixed before the numbers asked what happens when a symmetric indefinite factorisation does what production codes do: compute a fill-reducing order from the pattern alone, once, in a symbolic phase, and then pivot inside it, passing a planned pivot over only when the Bunch–Kaufman test refuses it. On a saddle-point family whose constraint rows have no diagonal the plan was followed at every step and cost nothing. On a grid made indefinite, with small entries scattered through its diagonal, the plan stopped fitting: its saving over the natural order fell from 31 per cent with no small entries to 3 per cent at three in ten, while re-reading the degrees at every step still saved 15.

The essay named the middle course and a prediction for it. “A code that kept the symbolic order but recomputed it for the remaining rows only when a pivot is refused would pay for re-ordering in proportion to the refusal count — nothing on the saddle family, a quarter of the steps at half the grid’s diagonal small. The prediction with a sign is that it recovers most of the step-by-step rule’s saving at a fraction of its re-ordering work, because the refusals cluster: once one small pivot is passed over, its neighbours’ degrees are what changed.”

That figure is the gap this essay sets out to close. At no small entries the two sparsity orders agree, because they read the same pattern; as the share rises, the fixed plan drifts up towards the natural order while the step-by-step rule holds down until a third of the diagonal is small. Everything between the two lines is saving a symbolic phase could have kept if it had known where the numbers would refuse it — and the question is whether it can be kept by noticing the refusals as they happen, without paying for a full re-read at every step.

The prediction holds up to a share of small pivots, and stops there. Past it, nothing does.

Four orders, one test #

The factorisation is the earlier essays’ symmetric $LDL^{\mathsf T}$ with the Bunch–Kaufman test at its usual constant, accepting a one-by-one pivot or a two-by-two block at each step. Only the order in which candidates are offered to the test changes:

Natural — rows in their given order. A plan fixed once — minimum degree computed from the pattern before any number is read, the order a symbolic phase hands to a numerical one. A plan redrawn at refusals — the same plan, but each time the pivoting criterion passes over the planned row, minimum degree is run again on the pattern of the rows that remain, as they now are after elimination, and the plan for the rest of the factorisation is replaced. The sparsest, every step — the degrees of every active row re-read before every pivot.

The cost of planning is counted in rows read. The fixed plan reads the pattern once, n rows. The step-by-step rule reads every active row at every step, $n(n+1)/2$ of them. The redrawn plan reads n rows once and then, at each refusal, the rows still active — so its cost is the original plan plus the sum of the active sizes at its refusals, which is what the prediction says should be small.

The matrices are the earlier essay’s: grids of 6 × 6, 8 × 8 and 10 × 10 whose Laplacian is made indefinite by alternating the diagonal’s sign over a sublattice, with a seeded share of the diagonal — none, 5, 10, 20, 30 or 50 per cent — set to $10^{-12}$; four seeds at each share, medians reported; and the saddle family, 24 variables with two, four or eight constraint rows.

Most of the saving, back #

The figure at the top of the page is the measure the prediction is about: of the saving the step-by-step rule makes over the natural order, what share each plan keeps.

The plan fixed once keeps less and less as small pivots are added. On the 8 × 8 grid it keeps 74 per cent at one small pivot in twenty, 63 at one in ten, 41 at one in five and 20 at three in ten. On 6 × 6 and 10 × 10 the same slide, to 45 and 36 per cent at three in ten.

The plan redrawn at refusals keeps 100, 85, 99 and 85 per cent on the 8 × 8 grid at the same four shares. On the 6 × 6 grid it keeps 97 to 118 per cent — on two shares it stores fewer entries than the step-by-step rule itself, since a minimum-degree plan looks further ahead than one greedy step. On the 10 × 10 grid it keeps 101, 98 and 93 per cent up to one in five, and then 66 at three in ten: the one cell in twelve where “most” is too strong a word.

In entries rather than shares, on the 8 × 8 grid at one in five: the natural order 498, the fixed plan 447, the redrawn plan 375 and the step-by-step rule 374. Turn the dial and the shape repeats on the other two grids. The fixed plan climbs towards the natural order as the share rises; the redrawn plan stays with the step-by-step rule; and at half the diagonal small all four lines meet — and the three sparsity orders cross above the natural one.

At a fraction of the reading #

The second half of the prediction is the cost. On the 8 × 8 grid the step-by-step rule reads 2,080 rows whatever the numbers; the fixed plan reads 64. The redrawn plan reads 231 at one small pivot in twenty, 344 at one in ten, 455 at one in five and 441 at three in ten — between 11 and 22 per cent of the step-by-step rule’s reading. On the 10 × 10 grid it reads 450 to 753 of 5,050 up to one in five, 9 to 15 per cent.

Rows read is a proxy for the work of ordering, and a generous one to the redrawn plan in one respect and harsh in another. A real minimum-degree code works on a quotient graph and does not read every active row to recompute a plan, so each re-plan costs less than counted; but a real code also has to rebuild its symbolic structures after a re-plan, which a count of rows does not include. What the count does show is the shape: the cost scales with the number of re-plans, which is small where the plan mostly holds, and with the active size at each, which is small for refusals late in the factorisation.

Each re-plan heads off the refusals after it #

The prediction gave a reason as well as a number: refusals cluster, so redrawing the plan after one should prevent the next. If that were false, the redrawn plan would re-plan exactly as often as the fixed plan is refused, and the reading would be the refusal count times the active size.

It is true at the shares where the redrawn plan works. On the 8 × 8 grid the fixed plan passes its planned row over at 7, 10, 14 and 17 steps as the share rises from one in twenty to three in ten; the redrawn plan re-plans 3, 7, 9 and 9 times. (The earlier essay counted departures from the plan a little more broadly, every row a refusal displaced, and got 7 to 21; the steps at which the test itself refused are the count that triggers a re-plan.) A redrawn plan, built from the active pattern after a small pivot has been passed over and paired, ranks that pivot’s neighbours by their real current degree, and the next few steps follow it.

The mechanism stops working where the method stops working. On the 10 × 10 grid at three in ten, the redrawn plan re-plans 17 times, as often as the fixed plan is refused, and recovers only 66 per cent. At half the diagonal small it re-plans 20 times against 19 refusals. When small pivots are a third or more of the diagonal there is no neighbourhood for a plan to settle — the next refusal is never far from the last — and a plan is redrawn only to be refused again.

A plan that looks further than one step #

Two cells in twelve show something the prediction did not mention: the redrawn plan storing fewer entries than the step-by-step rule it was supposed to approach from above. On the 6 × 6 grid at one in twenty it stores 167 against 170, and at three in ten 179 against 183. It is a small effect, and it has a clear cause. The step-by-step rule is greedy: at every step it offers the test the row of least current degree and takes the first that passes. A minimum-degree plan is the same greedy choice made in advance for every remaining step, with the elimination graph updated as each vertex goes, so its later choices see the fill its earlier ones create. When the step-by-step rule is forced off its greedy choice by a refusal, it simply takes the next sparsest; the redrawn plan takes the next row of a whole new ordering, built for the matrix as it now stands. Neither is optimal — the least fill there is searched every order of graphs of eighteen and twenty vertices and found minimum degree exact on small grids and up to 7.6 per cent above the best on random graphs, depending on how it broke its ties — and which greedy wins on a given matrix is a matter of a handful of entries.

What the two cells do say is that the step-by-step rule is not the ceiling the prediction treated it as. It is one heuristic among several that read the active pattern; re-reading it at every step is the most expensive way to use that information, not the only good one. How few columns the search needs made the unsymmetric version of the same point: a search over a single sparsest column captured most of what a full row-and-column search bought, at a fraction of its cost. Re-planning only at refusals is a search that is skipped whenever the last plan is still good enough to follow.

Where the plan holds, nothing changes #

The prediction’s other clause was that redrawing costs nothing on the saddle family, because there the plan is never refused. With four and eight constraints it is not, and the redrawn plan is the fixed plan to the entry — 65 and 80 entries against the natural order’s 113 and 161. With two constraints the criterion rejects one planned pivot, the plan is redrawn once, and the factor is the same 56 entries. The freedom a symmetric factorisation does not have found the structure that makes this so: a constraint row’s zero diagonal is filled in by its own variables, which a minimum-degree plan eliminates first for reasons of fill, so the test and the plan want the same order. A rule that re-plans only on refusal pays nothing there by construction, which is the property that would let a code use it unconditionally.

Half the diagonal small #

The refutation in this essay’s own prediction is at the top of the share range. “Most of the saving” assumed there was a saving to recover, and at half the diagonal small there is not: on the 8 × 8 grid the natural order stores 508 entries, the step-by-step rule 517, the redrawn plan 529 and the fixed plan 530. Every sparsity order is worse than none.

The growth figures say why it is not a stability problem. Growth stays between 1.2 and 1.7 for every order at every share, held there by two-by-two blocks — and the blocks are the cost. With half the diagonal tiny, the test accepts a small pivot only when paired with a neighbour, so nearly every step is forced to choose its pivot from the pairs the numbers allow rather than from the degrees, and an order computed from degrees, once or often, stops mattering. What the symbolic phase can only bound found the fill prediction under pivoting reduced to a bound; at half the diagonal small the bound is all there is, and the natural order happens to sit under it.

What a solver would change #

A production symmetric indefinite solver already has every piece of this. Its analysis phase computes a fill-reducing order — approximate minimum degree or nested dissection — and builds the elimination tree and the symbolic structure of the factor from it. Its numerical phase pivots inside that structure and, when the test refuses a pivot, delays it: the row is passed up the elimination tree to be tried again later, and the structure grows to hold the fill the delay causes. What it does not do is ask, at a delay, whether the order for what remains is still a good one. The measurement here says that asking — rerunning the ordering on the pattern that remains, at each delay — keeps most of the fill a full re-reading would save, for a cost proportional to the number of delays.

There are reasons a code might still not do it. Rebuilding the symbolic structure is more expensive than reading rows, and a code that parallelises over the elimination tree would lose the tree’s shape at every re-plan. The order decides the memory measured how much an ordering is worth in storage: a factor of 1.7 between the best and worst of four orders on one matrix. Here the difference between the fixed and redrawn plans is 447 against 375 entries at one small pivot in five — a fifth of the factor. Whether a fifth is worth a re-analysis depends on how many times the factor is reused, which is a property of the application rather than of the matrix.

The trade between sparsity and stability that this field began with — a threshold between fill and growth found it real on a grid built to make the two disagree — does not appear here either. Growth is the same under all four orders. What the redrawn plan buys is sparsity that the fixed plan lost by not knowing which pivots the test would refuse, and it buys it back without loosening the test. An ordering that does not wait for the numbers found families where the ordering could ignore the values entirely; this is the family where it cannot, and the cheapest way found so far to let the values in.

What these grids do not show #

Three grids, one sublattice pattern for the indefiniteness, small entries all of one size and scattered uniformly, four seeds. A real matrix’s small pivots are rarely uniform: they cluster in a region — a boundary layer, an incompressibility constraint over part of a domain — and clustered refusals are the case the prediction’s reasoning favours most. And the cost of a re-plan is counted in rows, not in the quotient-graph operations or symbolic rebuilds a production code would actually perform; the ratio would move, the ordering of the three methods by cost would not.

Still open: clustered small pivots, and a global constraint #

Small pivots in a region. Put the same share of small diagonal entries into one quadrant of the grid instead of across it. The prediction with a sign is that the fixed plan does worse there than when they are scattered, because a whole region’s ranking is wrong at once, and the redrawn plan better, because one re-plan at the region’s first refusal re-ranks all of it — so that the gap between the two widens, and the redrawn plan keeps its saving to a higher share than three in ten.

A constraint that couples distant variables. The earlier essay’s third question stands: a matrix with a global conservation law beside local constraints gives minimum degree a row whose variables are eliminated late for reasons of their own. Whether the fixed plan is refused there, and whether one re-plan repairs it, is the case that would test the local explanation of why the saddle family never refuses.