The column that was never fixed

A threshold between fill and growth measured one number deciding how small a pivot a sparse elimination will accept. On a convection grid with one ruinous corner entry, a threshold of 0.001 gave a small factor and a growth factor over a thousand, a threshold of 1 gave a large factor and growth near one, and the libraries’ default of 0.1 sat at most of both. The trade was the argument, and every essay on sparse pivoting since has been built on it.

Every one of them measured it with a rule that chooses rows only. At each step the column is the next one in order, and the rule takes the sparsest row whose entry in that column is at least τ times the column’s largest. The routine’s own description said so, and said in the same sentence that real codes choose the column too, “and doing so changes the constants and not the argument”.

That sentence was never measured. It is wrong in an informative way.

The Markowitz rule, stated #

Choosing rows and columns together is the Markowitz rule with a threshold. At every step it looks at every entry of the part of the matrix still to be eliminated. An entry is acceptable if it is at least τ times the largest entry in its own column. Among the acceptable entries it takes the one with the least Markowitz cost (r − 1)(c − 1), where r and c count the nonzeros in the entry’s row and column — the most new entries eliminating it could create. The row and the column are both moved to the front, so the factorisation is PAQ = LU rather than PA = LU.

The row-only rule is the same rule with the column fixed at the next index, and the implementation measured here is the same code with that one restriction, checked against the original row-only routine on every matrix and threshold: the same fill and the same growth factor to nine digits. So everything that differs below is the column choice and one other detail that turned out to matter more.

What the column buys on the conflict grid #

At τ = 0.1 on the 8×8 grid the row-only rule builds a factor of 875 entries with growth 38.5. The row-and-column rule builds 640 entries with growth 2.54. At τ = 0.001 the row-only rule has 741 entries and growth 2,209; the row-and-column rule, 640 and 2.54 again. At τ = 1 the row-only rule has 986 entries and growth 1.20; the other, 659 and 1.23.

Read along the thresholds, the solid curves are flat. The row-and-column rule’s factor holds between 640 and 659 entries at every threshold, and its growth factor is 2.54 at every threshold from 0.3 to 0.001 and 1.23 at 1. There is no trade left to make. The threshold that decided the row-only rule’s fate in both currencies decides almost nothing once the column is free, and loosening it costs nothing because the rule never takes the small pivots the loose threshold would allow.

The pivots show why. At τ = 0.001 the row-only rule accepts a pivot as small as 0.0011 of its column’s largest entry, and 42 of its 64 pivots are under a tenth. It is not doing anything wrong: in a fixed column the sparsest acceptable row is often one whose entry is small, and the threshold permits it. The row-and-column rule’s smallest pivot is a third of its column’s largest, and none is under a tenth. With every column of the remaining matrix to choose from, there is almost always an entry that is both as cheap as the cheapest and large in its column, and the rule finds it.

What happened to the ruinous corner #

The conflict grid was built so that the cheapest elimination at the first step — the corner node, with two neighbours — has a diagonal entry of 10⁻¹². Structure and stability stop being separable showed what taking it costs. Neither rule measured here takes it; both are thresholded. What they do instead differs, and it is not where one would guess.

The row-only rule, forced to eliminate column 0 first, takes the corner’s neighbour as the pivot row — an ordinary coupling entry of −1.5 — and then must eliminate column 1, then column 2, in the grid’s own order, each time taking the sparsest acceptable row in a column it did not choose. The corner is handled safely at step 0. The growth comes afterwards, from the columns the fixed order hands it.

The row-and-column rule eliminates the three other corners first, each on its own diagonal at a cost of four. At the fourth step it eliminates the ruinous corner’s column, pivoting on the same coupling entry of −1.5 in the row below it. The corner’s own row is not eliminated until step 35, by which time an earlier elimination has filled its diagonal with an ordinary number: the pivot it is finally eliminated on is −2.60.

So the tiny entry was never the difficulty either rule had to solve. The difficulty for the row-only rule was the order of the columns — a fixed order that is fine for the corner and poor for the rest of the grid.

The patterns make the fill difference visible. The row-only factor of the 6×6 grid has 372 entries with growth 38.5 at τ = 0.1: the lexicographic column order builds dense bands of fill that grow toward the bottom right, the familiar profile of a band-ordered grid. The row-and-column factor has 298 entries with growth 5.40, and its fill is concentrated in the last dozen rows — the pattern of an elimination that took the cheapest entries first, as a minimum-degree ordering would, while checking each against its column — the ordering the order decides the memory found beating the orderings with better asymptotics on a matrix of this kind. An ordering that does not wait for the numbers found a family where the ordering could be chosen for fill alone; this is the unsymmetric case doing something similar dynamically.

The size of the grid #

From 5×5 upward the row-only rule’s growth at τ = 0.1 is 38.5 on every grid, to three digits; the row-and-column rule’s is 1.00, 5.40 and then 2.54 on every grid from 7×7 to 10×10. The fill ratio grows with the grid under both rules, as fill in a two-dimensional grid must, and the gap between them widens: 111 against 99 entries on the 4×4 grid, 1,635 against 1,170 on the 10×10. By the largest grid the row-only factor is 40 per cent bigger.

The constant 38.5 is itself worth a sentence. A growth factor that does not change with the size of the problem is a property of a local pattern the fixed column order meets on every grid — the same few rows in the same arrangement near one boundary — and not of the problem’s size. It is what the row-only rule pays for being made to take the columns in an order it did not choose.

The tie-break, which does the rest #

Implementing the rule exposed a detail that the description above passed over. Markowitz costs are products of small integers, so many candidates tie. The row-only routine took the earliest row among equally cheap candidates. The row-and-column implementation took the one whose entry was largest relative to its column. Those are two changes, not one, and they can be separated.

On the conflict grid, each change helps and together they do all of it. At τ = 0.001 the row-only rule with earliest ties has growth 2,209; with largest ties, 1,545; the row-and-column rule with earliest ties, 21.9; with largest ties, 2.54. The column choice takes the first two decades and the tie-break the last one.

On random sparse matrices the two changes do not add, and one of them is harmful alone. At τ = 0.1 the median growth is 15.1 for rows only with earliest ties, 9.7 with largest ties, 24.8 for rows and columns with earliest ties, and 5.7 for rows and columns with largest ties. At τ = 0.001 the row-and-column rule with earliest ties has a worst case of 217,000, four times the row-only rule’s worst. Choosing the column without looking at magnitude gives the rule many more cheap candidates to choose among and nothing to prefer the safe ones by, and on a matrix with no structure the earliest cheap candidate is as likely to be small as large.

The fill is a different matter. Whichever way ties are broken, the row-and-column rule’s median fill on the random matrices is 109 to 115 against the row-only rule’s 214 to 253: the column choice halves it, and the tie-break does not move it. So the two halves of the argument come apart cleanly. Fill is bought by the column choice. Growth is bought by the tie-break, and the column choice only makes the tie-break more valuable.

A search for size that costs nothing #

The tie-break is a search for a large pivot, and searches for large pivots have been measured before. A pivot that searches one row and one column measured rook pivoting on dense matrices: walk from a column’s largest entry along its row to a larger one and back, until an entry is largest in both, and the growth factor falls from partial pivoting’s 4.06 to 2.53 at a cost of about three times the comparisons. Complete pivoting, which searches everything, reaches 1.88 at forty times the comparisons.

The magnitude tie-break is a search of the same kind with a different budget. It does not look for the largest entry anywhere; it looks among the entries that are already the cheapest by Markowitz cost and already pass the threshold, and it takes the largest of those relative to its column. The comparisons are ones the rule was making anyway — it had to compute every candidate’s cost and ratio to know which were cheapest and acceptable — so the search is free. What it cannot do is trade sparsity for size: a large entry with one more nonzero in its row is never considered.

That is why its effect depends on how many ties there are. On the conflict grid, whose interior rows and columns all have the same counts, a step can have dozens of candidates at the minimum cost, and the tie-break is choosing the largest of dozens. On a random sparse matrix with varied counts the minimum cost is shared by fewer entries, and the tie-break is choosing among a handful. That it still cuts the random matrices’ median growth by a factor of two to four suggests that even a handful of equally cheap candidates rarely all have small entries.

It also explains the one harmful combination. Freeing the column multiplies the number of cheap candidates. With a magnitude tie-break that is more choice among safe entries; with a positional tie-break it is more opportunities to take the first small entry that passes the threshold, and the threshold at 0.1 or 0.001 lets through entries that the swap that is not optional would recognise as the start of the trouble.

On matrices with no structure #

On random matrices the trade the earlier essay measured is still there under both rules: growth rises as the threshold falls, from median 1 at τ = 1 to 560 and 150 at τ = 0.001. What the row-and-column rule with the magnitude tie-break changes is its price. At every threshold its fill is half the row-only rule’s — 188 against 457 at τ = 1, 110 against 215 at τ = 0.001 — and its median growth is two and a half to four times smaller. Its worst case at τ = 0.001, 1,261, is forty times smaller than the row-only rule’s 54,484.

So the docstring’s sentence is half right about random matrices and wrong about the grid. On matrices without structure the threshold still trades fill for growth and the column choice changes where the trade sits. On the structured grid the rows-only rule’s trade was an artefact of being made to take columns in a fixed order, and it vanishes when the order is free. What the symbolic phase can only bound found the fill of threshold pivoting to be unpredictable before the numbers arrive; a rule that chooses columns dynamically makes it more so, since both permutations now depend on the values.

What codes do, and what this says about it #

Production unsymmetric sparse solvers do choose both. They search a small number of the sparsest columns rather than all of them, and they break ties among candidates of equal cost in various ways, commonly by magnitude. The measurement here says the second choice is not a detail. A rule that chooses columns and breaks ties by position can be less stable than a rule that chooses rows only; a rule that chooses columns and breaks ties by magnitude is both sparser and more stable at every threshold measured.

It also qualifies the threshold essay’s finding about the default. τ = 0.1 is where the row-only rule gets most of both, and that remains true of it. Under the row-and-column rule with the magnitude tie-break, on the grid, τ matters very little, and on random matrices it matters in the same direction as before but a factor of three less. The default was justified by a trade that a better rule makes smaller.

What this rests on #

Conflict grids from 4×4 to 10×10 with a drift of 0.5 and a corner diagonal of 10⁻¹²; twenty random 40 × 40 matrices with a nonzero diagonal and 8% off-diagonal density; thresholds from 0.001 to 1. The growth factor is the largest entry of any reduced matrix over the largest entry of A. The row-and-column rule searches every column at every step, which no production code does; a code searching only the few sparsest columns may find fewer large cheap candidates, and how many columns the search needs before the tie-break has something to choose among is not measured here. Every factorisation reproduces its matrix to 10⁻¹⁰ times its growth factor or better, and on the grid to 10⁻¹⁶.

The claims that have to fail #

The first is the sentence in the routine’s description: that choosing columns changes the constants and not the argument. On the 8×8 grid the row-and-column rule’s growth is 2.54 at τ = 0.001 and 1.23 at τ = 1; the refusal is fed the claim that the first exceeds the second a hundredfold, as it does for the row-only rule, and fails.

The second is the natural repair of the first: that freedom to choose the column is itself what makes the pivots safer. With ties broken by position, the row-and-column rule’s median growth on random sparse matrices at τ = 0.1 is 24.8 against the row-only rule’s 15.1; the refusal is fed the claim that it is no larger, and fails.

Still open: how few columns the search needs, and the symmetric case #

A search over a few columns. The rule here looks at every column. Codes look at a handful — the two or four sparsest — because a full search is quadratic per step. The tie-break’s value depends on how many equally cheap, large candidates the search can see, so the measurement to make is the growth and fill against the number of columns searched, on the grid and on random matrices, to find where the benefit saturates.

Symmetric indefinite matrices. A symmetric factorisation must permute rows and columns together, so the freedom measured here is not available: a diagonal pivot is chosen, or a two-by-two block, and the off-diagonal coupling the row-and-column rule used to step around the corner cannot be taken on its own. Whether the fixed-column rule’s trade returns for a symmetric version of the conflict grid under threshold Bunch–Kaufman pivoting, and what the two-by-two pivots cost in fill, is the case the order that was right last time and the quasi-definite family stepped around and nobody here has measured.