The baseline was the interchanges

A refusal has no fixed price laid a symmetric indefinite grid’s small diagonal entries out three ways — scattered, in a disc, along every other grid row — and factored each with a fill-reducing plan fixed once from the pattern, the Bunch–Kaufman test refusing the plan’s pivot wherever a small one came up. The plan’s factor barely noticed the layout: at three tenths small on the 10 × 10 grid it stored 898 entries for the scatter and 907 for the lines. The saving over the natural order did not agree. It was 8.9 per cent for the scatter and 19.2 for the lines, because the natural order stored 986 entries for one and 1,122 for the other. “Where the extra entries come from in the natural order is not measured here,” the essay said, and it proposed the obvious suspect. “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.”

Turning the lines is measured here, and it misses all three numbers. The suspect was wrong. The natural order’s extra entries on rows are measured too, and they come from somewhere the essay did not look: not from the direction the order runs, but from what the pivoting test does to the order as it runs.

Turning the lines #

The grid operator is the five-point Laplacian with the signs of its diagonal alternating like a chessboard, and it is the same matrix whichever way the grid is read: transposing the grid’s rows and columns permutes it into itself. So lines along columns are the row lines turned a quarter, seeded identically, the same thirty small pivots on the 10 × 10 grid at three tenths. Their pattern is the row lines’ pattern, entry for entry, because a small diagonal entry is still an entry; only its value has changed. The fill-reducing plan is read from the pattern alone, and on every seed and both grids it is the identical ranking for rows and for columns.

The natural order does fall, as predicted, from 1,122 entries to 1,008 — just short of the thousand the prediction asked for. The fixed plan does not stay where it was: it rises from 907 to 977, 7.7 per cent, with the same ranking read from the same pattern. And the saving goes not to the scatter’s 8.9 per cent but to 3.1, a third of it. Turn the dial back to rows and the three numbers return. The 8 × 8 grid agrees in part: the natural order falls from 545 to 515, the plan holds at 478 and 477, and the saving drops from 12.3 to 7.4 per cent.

At half small the move is larger. The natural order on the 10 × 10 grid falls from 1,192 to 1,030, and the plan rises from 1,053 to 1,255, so that a layout on which the plan saved 11.7 per cent becomes one on which it costs 21.8. The plan is not indifferent to which way the lines run, although it cannot see the lines: its ranking has a direction of its own, because minimum degree breaks its many ties on this grid by index, and the index runs along the rows.

The natural order is two orders #

The reason the natural order fell is not the one the prediction gave, and the way to see it is to notice that the natural order, as the factorisation here runs it, is not quite what its name says. It offers as the next pivot whatever row now sits at the next position. That is how a dense symmetric indefinite code proceeds: it works down the positions, and when the pivoting test refuses the diagonal entry at position $k$ it interchanges another row into place — the partner Bunch–Kaufman picks, or a two-by-two block of the two. The row it displaces goes to where the partner came from. From then on the positions are no longer the grid’s order. Each interchange rewrites the order that the rest of the factorisation follows.

The interchanges are not optional. When symmetry is not enough showed the smallest case: a symmetric matrix with a zero diagonal has no one-by-one pivot at all, and only a two-by-two block or a symmetric interchange gets past it. On these grids a small diagonal entry of $10^{-12}$ beside off-diagonals of one is that case to within rounding, so the test interchanges at every small pivot it reaches while the entry is still small, and on row lines at three tenths there are thirty small entries in a hundred steps. Each time, the positional order is rewritten.

The alternative is the natural order held to the grid’s index: the same matrix, the same test, the candidates always offered by their original label rather than their current position, so an interchange chooses the pivot and leaves the queue behind it as it was. That is the fixed plan’s mechanism with the identity as its ranking — a symbolic phase whose plan happens to be the grid’s own numbering.

The two differ, and the difference is the natural order’s extra entries. On the 10 × 10 grid with lines along rows, the positional order stores 70 entries more than the strict one at a tenth small, 59 at a fifth, 125 at three tenths and 191 at half. For every other layout the difference is smaller at every share from a tenth: along columns it is $-5$, 19, 36 and 62; scattered, $-2$, 23, 60 and 17; in a disc, 12, 0, 11 and 17. On the 8 × 8 grid the order is the same at every share from a tenth — the row lines’ interchanges cost 19, 37, 34 and 73 entries, more than any other layout’s — with smaller numbers throughout. At a twentieth small, where there is almost nothing to interchange, every layout’s difference is within sixteen entries either way.

So what the natural order paid for row lines was the interchanges. Held to the index it stores 997 entries on row lines at three tenths small, against 926 scattered, 972 along columns and 1,050 in a disc. Those four are within 13 per cent of each other where the positional order’s were within 14, but the row lines are no longer the outlier. They are second, behind the disc.

Across the shares the difference is a shape, not just a number. Offered by position, the natural order’s factor on row lines climbs from 1,005 entries at a twentieth small to 1,192 at half, the steepest of any layout. Held to the index the same lines store 1,004, 1,004, 998, 997 and 1,001 — flat to within one per cent across the whole range, as though the small entries were not there. The column lines and the scatter stay within about 6 per cent of their own starting points either way. The disc is the one layout whose strict factor does grow with the share, from 1,011 at a tenth to 1,061 at half, and its positional factor grows the same way, a few entries above: for the disc the growth belongs to the matrix, and the interchanges add almost nothing to it.

The interchange cost does not follow the number of interchanges either, which is the previous essay’s lesson about refusals arriving in a new place. At three tenths on the 10 × 10 grid the positional natural order takes 9 two-by-two pivots on the scatter, 8 on row lines, 9 on column lines and 12 in the disc, and the strict order is refused 17 times on the scatter against 3 on row lines. The row lines pay the most for their interchanges while having among the fewest. What an interchange costs must depend on where in the remaining order it sends a row. A row line has its small entries consecutive in the index, so its interchanges all fall in one stretch of the order, and each may displace a row the next few steps were about to need; that is a reading rather than a measurement, and the first prediction at the end of this essay is the measurement.

Two baselines, one plan #

Put the three numbers side by side and the earlier essay’s comparison changes shape. The fixed plan’s factors at three tenths are 898 scattered, 907 along rows, 977 along columns and 814 in a disc. Measured from the positional natural order the savings are 8.9, 19.2, 3.1 and 23.3 per cent; measured from the strict one, 3.0, 9.0, $-0.5$ and 22.5. The row lines’ saving halves. The scatter’s falls by two thirds. The column lines’ disappears. The disc’s barely moves, because the disc is the one layout whose positional and strict natural orders nearly agree — 1,061 and 1,050 — and its saving was the plan’s from the start.

On the 8 × 8 grid the strict savings are 1.4, 6.5, 2.9 and 6.7 per cent, against 3.0, 12.3, 7.4 and 10.2 from the positional order. The row lines’ advantage there halves too, and what remains of it is shared with the disc. On both grids, the strict baseline leaves the row lines with less than 55 per cent of the saving they appeared to have.

A small pivot with a small neighbour found that gathering small pivots into a disc kept the fixed plan close to its unperturbed saving, and the essay that followed found part of that reading was the baseline moving under it. Against a baseline that does not move with its own interchanges, the disc’s advantage on the 10 × 10 grid is the clearest result in the series: 22.5 per cent where no other layout reaches ten.

Why the plan cares which way the lines run #

The fixed plan’s ranking is the same for rows and columns, and yet it stores 907 entries for one and 977 for the other, refused 11 times for rows and 6 for columns. Fewer refusals and more fill: the previous essay’s finding that a refusal has no fixed price, seen again from a new angle. What differs between the two layouts is where the small pivots fall in the plan’s sequence. Minimum degree on a grid has thousands of ties — every interior point starts with four neighbours — and this implementation breaks them by index, which runs along the grid’s rows. Its ranking therefore has a grain, and lines that run with it meet the plan differently from lines that run across it.

Eliminating a vertex is a graph operation is what makes the ties so many. Eliminating a grid point joins its neighbours into a clique, and minimum degree picks the vertex whose clique would be smallest; on a fresh five-point grid every interior vertex has four neighbours, every edge vertex three, and the first choices are a tie among dozens. Each choice changes the degrees nearby and leaves the ties elsewhere standing, so the whole plan is a long sequence of choices that the heuristic did not make — the index made them. The least fill there is measured how far minimum degree sits from the true optimum on small graphs; the ties are where it is not even trying to be optimal, and a grid has more of them than any other graph.

Across the shares the plan’s response to turning has no single sign. On the 10 × 10 grid it stores 681 and 719 entries for rows and columns at a twentieth small, 762 and 767 at a tenth, 862 and 795 at a fifth, 907 and 977 at three tenths, and 1,053 and 1,255 at half: columns cost more at four shares of five, less at one, and the difference runs from 5 to 202 entries. On the 8 × 8 grid the two are within 7 per cent of each other at every share. A plan that does not see the small entries is still steered by them, through which of its tied choices they happen to sit under.

The same is true of the Bunch–Kaufman test itself. When it looks for the partner of a refused pivot it takes the largest entry in that pivot’s column, and on a five-point grid every off-diagonal starts at the same magnitude, so the first partner in position wins. Every tie in this factorisation — the plan’s, the test’s, the natural order’s — is broken by index. That is why the grid, which is symmetric under turning, does not factor symmetrically under turning, and why a quarter-turn of the small entries moves the plan by eight per cent on one grid and not at all on the other. Four seeds a cell show the plan’s factor for row lines at three tenths ranging from 897 to 1,036 between seeds. A difference of 70 entries between two orientations is a real difference on the median and within the spread of a single layout’s draws.

What the comparison should be #

An order fixed before the numbers introduced the fixed plan as what a sparse code actually does: compute an ordering from the pattern, then follow it, with the pivoting test allowed to delay a pivot it refuses. Measured against that, the fair comparison for a fixed plan is another fixed ranking — the strict natural order is exactly that, with the identity for its plan — and not an order that rewrites itself every time it interchanges. A saving computed against the positional natural order measures two things at once: how much fill the plan avoids, and how much fill the baseline’s own interchanges cause. On row lines at three tenths the second was more than half of the total.

That reaches back further than the last essay. A plan redrawn where it was refused measured how much of the fixed plan’s saving survives scattered small pivots, and how much redrawing the plan at each refusal wins back, both as fractions of a saving over the positional natural order. Its numbers are not wrong, but they are fractions of a quantity that includes the baseline’s own interchanges, and on the scatter at three tenths those are 60 of the 986 entries the baseline stores. Fractions of a moving quantity move with it. And an ordering that does not wait for the numbers framed the whole series’ question as a fight between an ordering chosen for fill and pivots chosen for stability. The positional natural order is the case where the fight is lost on both sides at once: an order chosen for nothing, rewritten by pivots chosen for stability, and paying fill for each rewrite.

The plan itself comes out of this better than it looked. Its factor is within 9 per cent of the strict natural order’s or better on every layout but one at three tenths small, and on the disc it is 22.5 per cent smaller. That is a modest claim for a fill-reducing plan on a 10 × 10 grid, and it is the honest one: the factor the plan avoids, measured against the factor the same mechanism stores without a plan.

What two grids do not show #

Two grid sizes, four seeds a cell, four layouts, five shares, and one implementation of every tie. A different tie-breaking rule — by degree then by a random permutation, as several codes do — would remove the grain from both the plan and the test, and the measurement here cannot say how much of the plan’s eight per cent between rows and columns would survive. The positional natural order is what a dense code runs; a sparse code with no ordering at all is rare, so the strict natural order is the more relevant baseline for sparse work and the positional one for comparing against dense. And the mechanism by which interchanges cost row lines more than any other layout is not measured: which interchanges, how far they move a row, and whether the cost is in the rows moved or in the rows overtaken.

Still open: how far an interchange moves a row, and a constraint that couples distant variables #

How far an interchange moves a row. The positional natural order’s extra entries on row lines are measured; their cause is not. The prediction with a sign is that on the 10 × 10 grid at three tenths small, the median interchange in the positional natural order moves a row by more than one grid row — ten positions — along rows and by fewer along columns, and that the extra entries are proportional, within a factor of two across the four layouts, to the summed distance rows are moved.

A constraint that couples distant variables. The earlier essay’s open question about a global conservation law still stands. This essay adds the baseline it should be measured against: the prediction is that against the strict natural order, the fixed plan’s saving with the global row present is within two points of its saving without it, while against the positional natural order it differs by more than five.