A small pivot with a small neighbour

A plan redrawn where it was refused took a symmetric indefinite factorisation’s fill-reducing order — minimum degree computed once from the pattern, before any number is read — and scattered small diagonal entries through the matrix until the pivoting test began refusing the plan. The plan fixed once kept 74 per cent of the step-by-step rule’s saving at one small pivot in twenty and 20 per cent at three in ten. Redrawing it for the remaining rows whenever the pivoting criterion refused the planned pivot kept 85 to 100 per cent, reading a tenth to a quarter of the rows the step-by-step rule reads.

Its open question moved the small pivots. “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.”

The figure at the top answers it on the 8 × 8 grid. The solid lines are the clustered layout and they sit above the dashed ones almost everywhere: the fixed plan does better in a cluster, not worse. The redrawn plan keeps a saving past three in ten, as predicted — 13.6 per cent with half the diagonal small, where scattered every plan stores more than the natural order. But it gets there by a different route from the one predicted, and the gap between the two plans narrows rather than widens.

The same matrices, the small pivots moved #

The factorisation is the earlier essays’ symmetric $LDL^{\mathsf T}$ with the Bunch–Kaufman test at its usual constant, which at each step either accepts the offered diagonal entry as a one-by-one pivot or pairs it with the row of its largest off-diagonal entry in a two-by-two block — or, if that partner’s own diagonal is large enough, pivots on the partner alone, which passes the offered row over. Four orders offer the candidates: natural; minimum degree fixed once; minimum degree redrawn for the remaining rows at each refusal; and the sparsest active row at every step.

The matrices are the earlier essay’s indefinite grids — a five-point Laplacian on 8 × 8 and 10 × 10 points with the sign of the diagonal alternated over a sublattice — with a share of the diagonal set to $10^{-12}$. Scattered, the small entries are chosen at random. Clustered, the same number are placed on the grid points nearest one centre, so they form a disc: thirteen points at a fifth of the 8 × 8 grid, a solid patch with a ragged edge. Each layout is drawn at four seeds and reported as medians, and each is compared against its own natural order, which stores a little more with the small entries clustered — 525 to 568 entries on the 8 × 8 grid against 495 to 512 scattered.

The dial shows the two layouts at the same share. Scattered, almost every small entry has four ordinary neighbours. Clustered, almost every small entry has at least one small neighbour, and those inside the disc have four.

Refused less, not more #

Scattered, the fixed plan is refused 7, 10, 14, 17 and 13 times on the 8 × 8 grid as the share rises from one in twenty to half, and 8 to 19 times on the 10 × 10. At the lowest share the count is more than twice the number of small entries — three small entries, seven refusals — because a refused row stays first in the plan and is offered, and refused, again at the next step, until elimination elsewhere has changed its diagonal enough to pass.

Clustered, the fixed plan is refused 0, 2, 2, 3 and 2 times on the 8 × 8 grid and 3 to 6 times on the 10 × 10. With half the diagonal small — thirty-two entries on the smaller grid — the plan is refused twice. The prediction was that a cluster would make the plan’s ranking wrong over a whole region at once. The plan’s ranking is the same in both layouts, because it is computed from the pattern and the pattern does not change; what changes is what the test does when the plan offers it a small entry.

Why: the test pairs them #

When the plan offers a small diagonal entry, the Bunch–Kaufman test looks at that row’s largest off-diagonal entry and its partner row $r$. If $r$’s own diagonal is large enough relative to $r$’s off-diagonals, the test pivots on $r$ alone, and the planned row is passed over: a refusal. If not, it takes the planned row and $r$ together as a two-by-two block, and the planned row has been pivoted on, in its planned place, inside the block.

Scattered, $r$ is nearly always an ordinary grid point with a diagonal of four, which passes, so the test takes $r$ and refuses the plan. Clustered, $r$ is usually another small entry, which cannot pass, so the test pairs the two. The figure counts it: the fixed plan takes more two-by-two pivots in the clustered layout at every share on both grids — 5 against 3 at a fifth on the 8 × 8 grid, 13 against 8 at three in ten on the 10 × 10 — and the refusals it does not have are the pairs it took instead. A cluster of small pivots is, to this test, a supply of partners for each other.

That is why the earlier essay’s mechanism does not transfer. It found re-planning effective because each refusal was a signal that the plan’s local ranking had been overtaken by the numbers. In a cluster that signal mostly does not fire: the numbers are absorbed into two-by-two blocks without the plan being contradicted.

What the fixed plan keeps #

The consequence for fill is in the figure at the top. On the 8 × 8 grid the fixed plan saves 29.7 and 28.7 per cent of the natural order’s factor at one and two small pivots in twenty when they are clustered, against 22.1 and 19.0 scattered. At a fifth the two layouts are level, 9.7 against 10.2. At three in ten the cluster keeps 10.2 per cent and the scattered layout 3.0; at half, 13.0 against a loss of 4.3. On the 10 × 10 grid the fixed plan saves more clustered at every share up to three in ten — 23.3 per cent against 8.9 there — and both layouts lose at half.

The prediction’s first half is therefore wrong in sign. A plan computed without the numbers is hurt most when the numbers are spread out, because every small entry is then an isolated contradiction the test resolves by passing the planned row over. Gathered together, the same numbers are resolved inside blocks the plan never had to know about.

The redrawn plan, and the greedy rule #

The redrawn plan saves 29.7 and 27.9 per cent clustered at the two lowest shares on the 8 × 8 grid, 17.8 at a fifth, 20.1 at three in ten and 13.6 at half. That last is the prediction’s second half holding: a saving kept past three in ten. But at a fifth it saves less clustered than scattered — 17.8 against 24.7 on the smaller grid, 21.7 against 25.7 on the larger — and the gap between the two plans, which the prediction expected to widen, is mostly narrower in the cluster: on the 8 × 8 grid a point or less at the lowest shares and at half, eight to ten points at a fifth and three in ten, against seven to fifteen points scattered below half. The redrawn plan’s advantage was its response to refusals, and a cluster supplies few.

The step-by-step sparsest rule, which re-reads every degree before every pivot and was the best order of all on the scattered grids, behaves differently again. Scattered, it stores at most one per cent more than the redrawn plan at any share and up to fourteen per cent less on the 10 × 10 grid at half. Clustered, it stores more than the redrawn plan at three in ten and at half on both grids — 504 entries against 448 and 512 against 491 on the 8 × 8, 898 against 840 and 1,047 against 916 on the 10 × 10 — and on the 8 × 8 grid at every lower share too.

A greedy rule chooses the sparsest row now, and inside a cluster that choice interacts with the pairing. The sparsest active row is often a small entry whose partner is another small entry; pairing them eliminates two rows with all their combined neighbours, which can create more fill than the minimum-degree plan’s choice of a row on the cluster’s edge. A plan computed from the whole pattern looks further ahead than one step, which a plan redrawn where it was refused offered as the reason its redrawn plan sometimes beat the greedy rule; in a cluster it is the usual case.

Where one re-plan still matters #

The cluster does not make re-planning pointless everywhere, and the exception is instructive. On the 10 × 10 grid with half the diagonal small, the fixed plan stores 1,159 entries against the natural order’s 1,078 — a loss of 7.5 per cent, worse than doing nothing — while the redrawn plan stores 916, a saving of 15. It got there with four re-plans against the fixed plan’s six refusals. Four re-rankings of the remaining rows were worth a fifth of the factor.

These measurements do not record where on the grid each refusal fell, so what follows is a reading rather than a result. The pairing argument says a small entry is passed over when its largest neighbour is ordinary, and inside a disc that happens only at the rim, where small entries sit beside ordinary ones. If that is right, a cluster changes where refusals happen, from everywhere to its edge, and their number with it: where the edge is short against the cluster’s area the fixed plan is almost never contradicted, and where it is long — half of a 10 × 10 grid is a disc that reaches the grid’s own boundary — refusals return and so does the value of redrawing. The reading makes a prediction that can fail, and it is the line layout in the open question below: a line is all edge, and the reading says it should be refused nearly as often as a scatter.

The numbers the earlier essays read #

This field began with the observation that structure and stability stop being separable: the sparsest pivot on a matrix with a small diagonal entry can be the one that ruins the answer. A threshold between fill and growth put a number on the trade, and what the symbolic phase can only bound showed that once pivoting enters, the pattern can only bound the fill, not predict it. Every essay since has been about how much of that bound a plan computed from the pattern can keep when the numbers interfere.

The cluster shows the interference depends on the arrangement of the numbers as well as their count. That is the same lesson the order that was right last time drew from reusing a pivot order across a sequence of matrices: what decides whether an order computed earlier still serves is not how much the numbers changed but whether the change lands where the order made its choices. A small pivot surrounded by large ones is a choice the plan made wrongly; a small pivot surrounded by small ones is, to the Bunch–Kaufman test, half of a block the plan did not need to foresee.

What re-planning costs here #

Fewer refusals means fewer re-plans, and so less reading. On the 8 × 8 grid the redrawn plan reads 64 to 214 rows clustered against 231 to 507 scattered, out of the 2,080 the step-by-step rule reads; on the 10 × 10, 191 to 252 against 450 to 1,298 out of 5,050. In a cluster the redrawn plan costs between three and ten per cent of the step-by-step rule’s planning work, and with one small pivot in twenty on the 8 × 8 grid it never re-plans at all, because it is never refused.

Growth stays small throughout, under 1.7 clustered and 2.0 scattered on every factorisation, so none of these orders buys its fill with stability. That was the pattern of the freedom a symmetric factorisation does not have: on these grids the Bunch–Kaufman test keeps growth bounded whatever order it is offered, and the orders differ only in fill.

What a solver should take from it #

A sparse symmetric indefinite code computes its ordering in a symbolic phase and lets the numerical phase delay pivots the criterion turns down, which is the fixed plan here. An order fixed before the numbers found that static ordering good on saddle-point matrices and poor with small pivots scattered; the redrawn plan repaired the scattered case. This essay adds that where the small pivots sit matters more than how many there are: the same share that cost the fixed plan nearly all its saving scattered costs it little clustered, because the test absorbs a cluster in two-by-two blocks.

That suggests reading the refusal count rather than the share. A solver that tracks how often the pivoting criterion passes its plan over knows, at no cost, whether its small pivots are behaving like a scatter or like a cluster, and only the first needs a re-plan. The redrawn plan already does exactly this — it re-plans only at refusals — which is why it is never worse than the fixed plan by more than two and a half points on these grids and costs almost nothing where refusals are rare. What the cluster removes is the reason to pay for the step-by-step rule at all.

What these grids do not show #

One family of grids, small entries of one size, one pivoting constant, two layouts with nothing between them. Small pivots clustered along a line rather than in a disc — a boundary layer, an interface between materials — would give each small entry two small neighbours rather than three or four, and the test’s pairing might then leave some unpaired; that layout is unmeasured. So is a cluster whose small entries are of mixed sign, which changes whether a pair’s determinant is large enough to accept. And four seeds at each share give a median that moves by a few entries from seed to seed; the differences reported between layouts are tens to hundreds of entries, well clear of that, but the smallest differences between the two plans in a cluster, a point or less, are within it.

Still open: a line of small pivots, and a global constraint #

Small pivots along a line. An interface puts its small entries in a row of grid points, each with exactly two small neighbours. The prediction with a sign is that the refusal count there sits between the disc’s and the scatter’s — roughly one refusal for every three small entries, from the pairs a line cannot complete at its ends and wherever the plan offers two of its points out of order — and that the fixed plan’s saving at three in ten is likewise between the two layouts’.

A constraint that couples distant variables. The earlier essays’ third question still 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.