A refusal has no fixed price

A small pivot with a small neighbour gathered a grid’s small diagonal entries into a disc and found the fill-reducing plan, computed once from the pattern, refused far less often than when the same entries were scattered — 0 to 6 times against 7 to 19 — and saving far more at three in ten: 10 and 23 per cent of the natural order’s factor against 3 and 9. The reason was in the Bunch–Kaufman test. A small pivot whose neighbour is also small cannot be passed over for that neighbour, so the test pairs the two into a two-by-two block and keeps the planned row.

Its essay asked about the layout between. “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’.”

The rate holds. The ordering mostly holds. And the comparison of savings, measured another way, says that the refusal count was never the plan’s cost.

Three layouts of the same small pivots #

The matrices are the earlier essays’: a symmetric indefinite grid of $k \times k$ unknowns, five-point coupling, diagonal entries of alternating sign, and a share of the diagonal replaced by $10^{-12}$. Scattered, the small entries go to random grid points; in a disc, to the points nearest a random centre; along lines, to whole grid rows, every other row so that no two lines touch, filled one line at a time from a seeded starting row — on the 8 × 8 grid four lines hold half the diagonal. Each matrix is factored four ways: in the natural order, by a minimum-degree plan fixed once from the pattern, by that plan redrawn wherever the pivoting test refuses it, and by the sparsest pivot at every step. Every count is a median over four seeds.

One refusal in three #

Along lines the fixed plan is refused 1, 2, 4, 8 and 10 times on the 8 × 8 grid at 5, 10, 20, 30 and 50 per cent small — 3, 6, 13, 19 and 32 small entries — and 2, 4, 5, 11 and 20 times on the 10 × 10 grid with 5, 10, 20, 30 and 50 of them. Per small entry that is between 0.25 and 0.42 on every cell, around the one in three the prediction gave. The scatter runs from 0.4 to 2.3 refusals per small entry, falling as more of its small points happen to have small neighbours; the disc from 0 to 0.8, under 0.2 on half its cells.

The ordering the prediction expected is there on seven cells of ten. On the 10 × 10 grid it fails three ways: at 5 and 20 per cent the line is refused less than the disc, 2 times against 4 and 5 against 6, and at half small more than the scatter, 20 times against 19. A line’s points pair along it, so most of its small entries are absorbed into two-by-two blocks the way a disc’s are, and its refusals come where the planned order reaches a point whose partner on the line has already been eliminated — the unpaired ends and the gaps the plan leaves. That rate is steady at about a third; the disc’s and the scatter’s rates are not steady at all, so whether the line falls between them depends on the cell.

The refusals are not the cost #

The earlier essays priced each layout by its saving over the natural order, and that is a ratio of two factors that both depend on the layout. The plan’s own cost is cleaner: the entries the small pivots add to the fixed plan’s factor, over the same plan’s factor on the same grid with no small pivots at all — 358 entries on the 8 × 8 grid, 655 on the 10 × 10.

The figure at the top of the page is that cost on the 8 × 8 grid. At 30 per cent small the scatter adds 122 entries, the lines 120 and the disc 146; they were refused 17, 8 and 3 times. At half small, 172, 163 and 136, refused 13, 10 and 2 times. At a fifth, 89, 95 and 118, refused 14, 4 and 2 times. On the 10 × 10 grid at 30 per cent, 243, 252 and 159; at half, 403, 398 and 504; at a fifth, 260, 207 and 206. From a fifth of the diagonal upward, on both grids, the three layouts’ costs are within a factor of 1.6 of each other at every share while their refusal counts differ by a factor of three to seven. At three in ten on the 8 × 8 grid the disc, refused least, costs most.

Below a fifth the layouts do differ: at a tenth on the 8 × 8 grid the disc adds 15 entries where the scatter adds 55 and the lines 50. With few small pivots, a compact disc touches few columns of the plan; with many, every layout touches most of them.

Divided out, a refusal has no fixed price. A scattered layout’s refusals cost 5.5 to 21 entries each; a line’s 15 to 41; a disc’s 7.5 to 84. The disc is refused rarely and each refusal it does make, or rather the pairing that prevents the others, comes with a large reorganisation of the plan’s tail. The count of refusals is the number of times the test intervened, and the fill is what the factorisation pays for the pivots it ends up taking, one-by-one or two-by-two, whether or not the test had to intervene to take them. A disc’s small pivots are paired without a refusal, because each has a small neighbour to pair with, but the pairing still reorders the plan’s elimination around the disc, and that costs fill the refusal count never records. An ordering that does not wait for the numbers described the conflict as memory decided by the pattern and stability by the values; a pairing is the values overruling the pattern silently, and the fill it causes is real whether or not anything was refused.

The price is per small pivot #

If a refusal has no fixed price, something else should, and the obvious candidate is the small pivot itself. Divided by the number of small entries rather than the number of refusals, the fixed plan’s extra entries are 6.8, 7.3 and 9.1 apiece on the 8 × 8 grid at a fifth small, scattered, along lines and in a disc; 6.4, 6.3 and 7.7 at three in ten; 5.4, 5.1 and 4.3 at half. On the 10 × 10 grid, 13.0, 10.3 and 10.3; 8.1, 8.4 and 5.3; 8.1, 8.0 and 10.1. At each share and grid the three layouts’ prices per small pivot are within a factor of 1.6 of each other, where their prices per refusal spread by a factor of 2.5 to 9.3.

So a small pivot costs the fixed plan four to thirteen entries wherever it sits, from a fifth of the diagonal upward, and a code estimating what its plan will pay could count the small diagonal entries before factoring and be closer than by counting the test’s interventions afterwards. The price falls with the share on the 8 × 8 grid, from about seven to about five, because with more small pivots more of them share their cost: a two-by-two block pairs two of them at once, and at half small most are paired. The 10 × 10 grid does not fall so cleanly, and its larger factor leaves room for the layouts to differ more; four seeds a cell are not enough to say whether its price is flat or falling.

The baseline moved #

So the earlier essay’s saving moved for another reason. The natural order’s factor is not a fixed yardstick: it is a factorisation of the same matrix with the same pivoting test, and the small pivots change it too. On the 10 × 10 grid at 30 per cent small the natural order stores 986 entries with the small pivots scattered, 1,061 in a disc and 1,122 along lines; on the 8 × 8 grid, 495, 561 and 545. The natural order meets lines along the grid’s rows one after another, and its factor grows most for them; it is not through taking more two-by-two pivots, since on the 8 × 8 grid at three in ten it takes 6 along lines against 5 scattered and 8 in a disc. Where the extra entries come from in the natural order is not measured here. What is measured is that they are the natural order’s, and that the fixed plan’s factor barely notices the difference.

Put side by side, the two measures disagree. On the 10 × 10 grid at three in ten the lines save 19.2 per cent of the natural order’s factor and the scatter 8.9 — more than twice as much — while the fixed plans store 907 and 898 entries, the lines 1 per cent more. The disc saves 23.3 per cent and its plan stores 814, which is genuinely less. On the 8 × 8 grid the lines save 12.3 per cent and the disc 10.2, where the disc’s plan stores 504 entries and the lines’ 478. So of the earlier essay’s two findings at three in ten, the 10 × 10 one stands — the disc’s fixed plan is the smallest — and the 8 × 8 one does not: there the disc’s plan is the largest of the three, and it looked best because the natural order did worst.

The redrawn plan agrees #

The plan redrawn at every refusal is a second check, since it reacts to refusals by construction. On the 10 × 10 grid at three in ten it is redrawn 17 times with the small pivots scattered, 13 along lines and 3 in a disc, and stores 825, 819 and 840 entries: within 3 per cent of one another, after redraw counts that differ by almost six times. On the 8 × 8 grid it stores 432, 489 and 448, redrawn 9, 11 and 5 times — and along lines the redrawn plan stores more than the fixed one, 489 against 478, so eleven redraws bought nothing there. At half small on the 10 × 10 grid the spread opens, 1,031, 1,115 and 916, and the disc, redrawn only four times, stores least.

The step-by-step sparsest rule, which reads every remaining degree at every step and so reacts to everything, does not agree with either: on the 10 × 10 grid at three in ten it stores 743 entries scattered, 947 along lines and 898 in a disc. The least fill there is found that greedy rule close to the optimum on small graphs with no pivoting in the way; with the pivoting test in the way, how close it comes depends on the layout far more than the plans do, and the refusal count predicts its ranking no better than theirs.

What the plan should be judged by #

A saving over the natural order answers whether to use the plan, which is a fair question for a code to ask, but it does not compare layouts, because the denominator is itself a factorisation that the layout changes. The quantity that compares them is the plan’s own factor, or its excess over the same plan with nothing small. An order fixed before the numbers and a plan redrawn where it was refused measured their plans against the step-by-step sparsest rule as well as the natural order, and both baselines move with the matrix in the same way; the conclusions there that compared a plan with a rule on the same matrix are unaffected, and the ones that compared one matrix’s saving with another’s are the ones to reread.

The refusal count is still worth having: it is how often the test had to override the plan, and a plan redrawn where it was refused used it as the trigger for redrawing, which works whatever a refusal costs. What it is not is a price. A threshold between fill and growth set the test’s threshold as a trade between the two, and structure and stability stop being separable began this line of essays with the observation that a sparse pivot order and a stable one are decided together; the refusal count records the moments they disagreed, not the amount it cost to settle each disagreement. The freedom a symmetric factorisation does not have found the symmetric factorisation unable to choose its pivots freely, and the small pivots it must pair cost the plan fill whether the pairing was the plan’s idea or the test’s.

What a code can take from this #

Count the small pivots, not the refusals. The entries a fixed plan loses to small diagonal entries track how many there are, within a factor of 1.6 across three very different layouts, and not how often the pivoting test overrode the plan, which varied three to seven times for the same cost.

Judge a plan by its own factor. A saving over the natural order is the right number for deciding whether to use the plan on a given matrix, and the wrong one for comparing two matrices, because the natural order’s factor moves with the matrix by as much as the plan’s saving does.

Redraw anyway. The plan redrawn at refusals stored within 3 per cent across layouts on the 10 × 10 grid at three in ten, and below the fixed plan on nine of the twelve layout-grid cells measured at three in ten and at half small. A refusal is a poor price and a good trigger.

What two grids do not show #

Two grid sizes, one coupling, one size of small entry, four seeds a cell and medians over them; with four seeds a median moves by a refusal or two, and the claims above are made on differences larger than that. The excess is measured from the fixed plan on the same grid with nothing small, which is one factorisation of one matrix and a fixed point to measure from, unlike the natural order, but it is still a choice of yardstick; a different one would shift every layout’s excess by the same number of entries and leave the differences between them as they are. One threshold for the Bunch–Kaufman test, the standard $\alpha \approx 0.64$; a looser one would refuse less and pair less, and could change which layout pays most. One kind of line, along grid rows; lines along columns would meet the natural order across rather than along, and the prediction is that the natural order’s factor would then not grow, which would move the lines’ saving down to the scatter’s without changing the fixed plan at all.

Still open: lines across the grain, and the global constraint #

Lines across the grain. If the lines’ large saving is the natural order’s poor factor on rows, turning the lines to run along columns should remove it. The prediction with a sign is that on the 10 × 10 grid at three in ten, lines along columns leave the fixed plan’s factor within 3 per cent of the row lines’ 907 entries and bring the natural order’s factor down below 1,000, so that their saving falls to within two points of the scatter’s 8.9 per cent.

A constraint that couples distant variables. The oldest open question about minimum degree still stands: a global conservation law beside local constraints gives minimum degree a row whose variables are eliminated late for their own reasons. The prediction is that the fixed plan is refused there no more than on the grid without it, and that the row’s elimination adds more entries than all the refusals together — a second case where the refusal count and the cost part company.