How few columns the search needs

The column that was never fixed found that choosing the pivot’s column as well as its row changes the argument rather than the constants, and that what does most of the work is not the column but which of several equally cheap entries is taken. It also left a gap between what it measured and what any library does. Its rule looks at every active column at every step, and a search over every column is quadratic in the size of the active submatrix — so the rule as measured is not a rule anybody ships.

What codes ship is a handful. Two, four, eight of the sparsest active columns are examined and the best acceptable pivot among those is taken, on the reasoning that the sparsest columns are where the cheap pivots are and the rest are not worth visiting. A threshold between fill and growth is where the other number in this rule — how small a pivot the elimination will accept — was priced, and it is held at the library default of a tenth throughout unless a figure says otherwise.

That reasoning is a claim about a distribution and it has never been checked here. The measurement is one sweep: the same factorisation, with the search limited to the few sparsest columns, over widths from one to every column.

One column is four fifths of it #

Over eighty random sparse 40 by 40 matrices at the library default threshold, taking the sparsest acceptable row in a fixed column — no column search at all — gives a median fill of 244. Searching every column gives 109.

Searching one column gives 136.

That is 80 per cent of the distance between the two, bought by a scan that is linear in the active submatrix rather than quadratic in it. The rest of the sweep fills in the curve: 127 at two columns, 123 at three, 121 at four, 119 at six, 117 at eight, 114 at twelve, 110 at sixteen, and 109 from twenty-four onward, which is every column that exists at most steps.

So the shape is a steep first step and a long shallow tail, which is what the library heuristic assumes and is not obviously what it would find. The alternative shape — a benefit spread evenly over the columns, so that looking at four gets four times what looking at one gets — would have made the narrowing a real sacrifice. It does not happen.

The share is stable where it matters. Repeating the sweep at five thresholds from partial pivoting down to a thousandth, one column captures 79, 83, 80, 89 and 92 per cent of what the full search buys. It rises as the threshold loosens, which makes sense: a looser threshold accepts more candidates, so a single column is more likely to contain one of the cheap ones. That the fill a factorisation ends with is a property of the order it eliminates in rather than of the matrix is the order decides the memory; what is being narrowed here is the search for that order and not the order itself.

The growth was bought at the first column too #

The median growth factor runs 7.33, 8.00, 7.29, 6.77, 6.55, 6.43, 6.21, 6.68, 6.33 and 6.33 across the widths, against 15.07 with no column search at all.

Reading that as a curve is a mistake and reading its endpoints is not. The endpoints say the column rule halves the median growth and one column has essentially all of the halving; the middle says nothing, because the differences between adjacent widths are smaller than the differences between neighbouring draws of the same experiment. The same caution applies to a growth factor wherever it is reported, and what the symbolic phase can only bound prices the gap between what a count predicts and what a factorisation with pivoting in it delivers.

That is worth being explicit about because the fill curve is readable at that resolution and the growth curve is not, and the two are drawn on the same axes. A median fill of 119 against 117 is two entries in a factor of some hundreds and reproduces; a median growth of 6.55 against 6.43 does not.

So the summary of the first two readings is short. The column rule’s benefit, in both fill and growth, is bought almost entirely by the first column the search is allowed to look at, and everything after it is the last fifth of the fill at a quadratic price.

The reading that changes its mind #

The third curve on the figure is the worst growth in the sample, and it is the one that looked like the most interesting result here before it was checked.

At the default threshold it runs 42.0 at one column and 247.2 at every column. The narrow search’s worst case is six times better than the full search’s, which is a striking thing to find — a cheaper rule that is also safer — and it has a mechanism ready to hand. A wider search sees more candidates of equal Markowitz cost, the tie-break takes the largest of them, and largest-among-more is not the same as large.

Repeated on four further independent sets of eighty matrices, the ratio of the two worst cases is 2.19, 0.75, 0.80 and 0.50.

It crosses one in both directions and spans a factor of thirteen. There is no ordering of the two searches on the worst case, and the factor of six the first draw showed is a property of that draw.

The reason is not subtle once it is stated. A worst case over eighty samples is an order statistic — the maximum of a heavy-tailed quantity — and the maximum of eighty draws has enormous variance whatever its distribution. The median has one value’s worth of noise in it; the maximum has the whole tail’s.

So the honest report of the third curve is that it cannot be read, and the useful thing is the check. A sweep run once, at one seed and one threshold, would have reported a cheaper rule that is also safer, with a plausible mechanism attached. Four more seeds cost four more runs of a measurement that takes seconds, and they are the difference between a finding and an anecdote.

The width is worthless without the tie-break #

Every number above is measured with ties in the Markowitz cost broken by taking the largest of the equally cheap candidates. That choice was found to matter by the column that was never fixed, which reported that what does most of the work is not the column but which of several equally cheap entries is taken. Sweeping the width with the other tie-break says something sharper than it matters.

The fill is almost unchanged. Taking the earliest tied candidate instead of the largest gives 138, 126, 124, 123, 120, 116, 115, 112, 110 and 110 against the largest-tie sequence’s 136, 127, 123, 121, 119, 117, 114, 110, 109 and 109. The two agree to within a couple of entries at every width, and neither is consistently above the other.

The growth is a different measurement entirely. It runs 12.60, 16.32, 19.37, 20.76, 21.23, 21.55, 17.18, 22.26, 19.96 and 17.64.

It rises with the width, and from two columns onward it is above the 15.07 that looking at no columns at all produces. So on these matrices, widening the search while breaking ties by position makes the arithmetic worse than not searching columns at all, the whole way to the full search, while the fill falls exactly as it does under the good tie-break.

That is the shape worth carrying out of this sweep. The two rules are indistinguishable on the quantity a sparse-factorisation survey reports and opposite on the quantity a solve fails on. A code that widened its search and reported the fill it saved would have a perfectly honest improvement to show and an elimination three times as likely to lose digits.

The mechanism is the one the earlier essay named, seen from further along. The Markowitz cost is a product of two small integers, so it ties constantly — and a wider search does not merely find cheaper candidates, it finds more candidates at the same cost. Widening therefore amplifies whatever the tie-break does, in whichever direction it does it. Taking the largest means a wider search has more large entries to choose the best of; taking the earliest means it has more entries whose only qualification is their position, and the more of them there are the less the one taken has to recommend it.

So the width and the tie-break are not two independent settings to tune. The width is a multiplier on the tie-break, and its sign is the tie-break’s.

Where one column is not enough #

The random survey’s answer is not the whole answer, because the matrices in it have no structure and the failure this rule exists for does.

On the 8 by 8 conflict grid — the family built so that the sparsest pivot and the largest pivot are never the same entry — one column behaves quite differently. Its growth is 7.37 at a threshold of three tenths, 7.59 at a tenth, and 40.54 at a hundredth and below.

Two columns give 2.5417. At every one of those thresholds, to four figures.

That flatness is the whole of what the column rule buys on this family. The column that was never fixed reported the growth staying at 2.54 at every threshold from three tenths down to a thousandth where the row-only rule climbed to 2,209, and read it as what searching the columns achieves. It is what searching the second column achieves. The third onward contribute nothing measurable — their curves are the same four digits — and the first alone does not get there.

So the two families give two different answers to the same question, and both are useful. On matrices with no structure, one column is four fifths of the benefit and the rest is a long tail. On a matrix built to defeat the rule, one column is a failure, two are complete, and there is nothing in between.

A code that has to work on both therefore wants two, which is at the low end of what libraries actually use and is the first number this measurement would have suggested on its own.

Why the second column is the one that matters #

The conflict grid’s structure says why, and the reason generalises further than the family does.

Its construction puts the cheap pivot and the large pivot in different columns by design. A search that sees one column sees one of those two and is forced to take whichever it has: a cheap pivot that is numerically bad, or an acceptable pivot that is expensive. Which one it gets depends on which column happened to be sparsest, and that is why its growth moves with the threshold — the threshold decides whether the cheap one is acceptable.

A search that sees two columns sees both, and can take the cheap-and-acceptable pivot when one exists. Once it can, nothing a third column offers improves on it, because the grid has no third kind of entry.

The generalisation is that the width a search needs is the number of kinds of candidate the matrix presents at a step, not the number of columns it has. Random matrices present one kind — a jumble in which the cheap and the large are uncorrelated — so one column is nearly enough. The conflict grid presents two, so two columns are exactly enough. That a family can be built in which the two objectives are systematically opposed is what makes it worth having beside the random survey, and it is the same role an ordering that does not wait for the numbers gives the family on which they are not opposed at all. A family presenting three would need three, and nothing here says how to recognise one in advance.

What must fail for any of this to be wrong #

Six claims and a refusal. That one column captures more than three quarters of the fill benefit the full search buys, at every one of five thresholds. That it also takes most of what the column rule buys over no column search at all. That the median fill falls as the search widens and never rebounds by more than a few per cent of its own running least — stated that way rather than as strict monotonicity, because a median over eighty draws wobbles and does at partial pivoting, 184 then 185. That the median growth at one column and at every column differ by less than half of what the column rule bought. That on the conflict grid two columns hold the growth at one number at every loose threshold, and one column does not. And that the worst growth does not order the two searches consistently across draws.

The refusal is fed the claim that the narrow search has the better worst case on every draw, and required to fail.

That last pair is the unusual shape here, and it is deliberate. The requirement and the refusal are about the same quantity in opposite directions: the first needs the ratio to cross one, and the second is handed the statement that it never does. Both would pass on the first draw alone.

What this does not settle #

One size, one density, one family of random matrices, and one structured family. Forty by forty at eight per cent density is small enough that “every column” is about twenty-four at most steps, so the widths above twelve are barely distinguishable from a full search by construction. Whether the first step stays as steep at a size where a full search is genuinely expensive is the question the least fill there is runs into from the other side, where an exact search over every elimination order is affordable only to twenty vertices.

The cost of the search is argued and not measured. A one-column scan is linear in the active submatrix and a full search quadratic in it, and that is why the narrowing exists — but the constant in front matters at these sizes and nothing here times anything. The quadratic term dominates at a size this experiment does not reach.

And the columns are chosen as the sparsest at each step, which is itself a sort. A code that keeps the active columns in a heap pays for maintaining it, and one that rescans pays a linear cost to find the sparsest few — the same bookkeeping an ordering that buys processors, not time leaves out of its own critical path, for the same reason. Which of those a real implementation does changes what “one column” costs, and neither is modelled.

Still open: a third kind of candidate, and the width a code could choose for itself #

A family that needs three columns. The argument above says the width a search needs is the number of kinds of candidate a step presents, and it has two data points: a jumble that needs one and a grid built around a pair that needs two. A family constructed with three distinct kinds — cheap and unacceptable, acceptable and dear, and a third that is neither — would test whether the count is really the mechanism or whether two is simply where the benefit stops on everything. It is a construction rather than a sweep, which is why it is not here.

A width chosen at each step rather than fixed. Every measurement above fixes the width for a whole factorisation. A search that stopped as soon as it found an acceptable pivot at the least Markowitz cost seen so far would take one column on most steps and more on the few that need it, and its cost would be the average rather than the worst. Whether that average is near one on the conflict grid — where only some steps present the conflict — is the measurement that would turn the finding into a rule a code could use.

The tail, with enough samples to read it. The worst-case reading fails at eighty matrices and the failure is a property of the sample size rather than of the quantity. What number of draws would give a stable ordering, or whether the distributions genuinely overlap so that no number would, is answerable by running the same sweep at several sample sizes and watching the spread of the ratio. If it narrows like the square root of the count the question is affordable; if it does not, the two searches have the same tail and that is the answer.

And the same narrowing on the symmetric rule. A symmetric factorisation permutes rows and columns together, so there is no separate column to search and the freedom measured here does not exist in the same form. What it has instead is a choice between a one-by-one and a two-by-two pivot, and whether a narrowed search over candidate diagonal blocks behaves like this one is the case the order that was right last time and the quasi-definite family both stepped around.