The freedom a symmetric factorisation does not have

Every measurement in this field so far has been of an unsymmetric elimination, where the pivot’s row and its column are two separate choices. The column that was never fixed found that taking both rather than one changes the argument, and how few columns the search needs found that most of that change is bought by the first column the search looks at.

A symmetric factorisation has none of it. To keep the factor symmetric the same permutation must be applied to the rows and to the columns, so the pivot is a diagonal entry — and the off-diagonal entry the row-and-column rule used to step around a conflict cannot be taken on its own, because taking it would destroy the symmetry the factorisation exists to exploit.

That is strictly less freedom, and the expectation follows: the conflict between sparsity and stability should be at least as sharp here, probably sharper, and an ordering chosen for fill should pay for itself.

It does not. On the family where the difficulty is worst, the ordering chosen for sparsity is better on fill and better on growth, at every setting of the pivot test.

The family where the diagonal is not small but absent #

The unsymmetric conflict grid was built to order: its corner entry is made tiny so that the sparsest pivot is the one a stable rule must refuse. The symmetric case does not need constructing, because a standard problem already has the difficulty in a worse form.

A saddle-point matrix — an interior operator, a constraint block, and a zero block where the constraints meet each other — has no diagonal entry at all in its constraint rows. Not small: absent. A one-by-one pivot there is not a bad choice, it is a division by zero, and no threshold however loose makes it legal.

The matrix measured here has twenty-four interior unknowns on a tridiagonal operator and four constraint rows of three nonzeros each. All four of its constraint diagonal entries are zero.

And the constraint rows are also among the sparsest rows in the matrix — three nonzeros, the same as an interior row. So a rule that chooses the sparsest available pivot is being offered, at every step, rows on which no pivot exists. That is the conflict grid’s arrangement arrived at by the problem rather than by construction, and it is sharper, because the unsymmetric grid’s bad pivot was merely tiny.

What makes the factorisation possible at all is the two-by-two block. Bunch and Kaufman’s test decides at each step between a single diagonal entry and a two-by-two block straddling the diagonal, and a block has a determinant even when both its diagonal entries are zero. The constant in the test is how much is demanded of a diagonal entry before it is accepted alone: loose, almost anything passes; strict, almost everything becomes a block.

Better on both currencies #

Two orders are compared. The natural one takes the diagonal entries in the order they arrive. The other takes, at each step, the one of least degree in what remains — the symmetric analogue of a Markowitz choice, with the column count and the row count being the same number because the matrix is symmetric.

At the classical setting of the test, the natural order produces a factor of 113 entries with a growth of 1.83. The sparsest order produces 70 entries with a growth of 1.28.

Thirty-eight per cent fewer entries and thirty per cent less growth, from the same matrix, by the ordering alone.

That result survives the density of the constraint rows. At two, three, four and six nonzeros a constraint row, the sparsest order holds 74, 72, 74 and 86 entries against the natural order’s 111, 113, 118 and 142, and its growth is never worse by more than a fifth.

The density is worth sweeping rather than fixing because it is the one thing about a saddle-point matrix a modeller controls. A constraint touching two unknowns is a link between two nodes; one touching six is a condition over a patch, and a real problem has some of each. What the sweep says is that the ordering’s advantage is not an artefact of very sparse constraints: at six nonzeros a row the factor is half again as large and the gap between the orders is wider in absolute terms, 56 entries against 41.

The count of blocks does move with the density, and not monotonically: at two nonzeros a row the sparsest order takes none, at three it takes one, at four two, and at six one again. That number is set by how many of the constraint diagonals the Schur complement happens to leave small, which is a numerical accident of each matrix rather than a property of the family — and it is the one column in this measurement that should not be read as a trend.

So the answer to the question is that the conflict does not carry over. The reason is worth more than the answer.

The zero diagonal is only zero at the start #

A constraint row has no diagonal entry in the matrix as given. It does not follow that it has none when the factorisation reaches it.

Eliminating an interior unknown updates every remaining entry, and the update to the constraint block is exactly the Schur complement the constraints acquire once the interior has been solved out. That object has a diagonal, and it is generically nonzero. So the difficulty a saddle-point matrix presents is not distributed over the factorisation — it is concentrated at the beginning, and it evaporates as the interior is eliminated.

Which means the sparsest-available rule is not solving the conflict by being clever about it. It is deferring it. Choosing least degree happens to put the constraint rows late, because a constraint row’s degree grows as the interior rows next to it are eliminated while an interior row’s degree stays near three until its own neighbourhood is reached.

The numbers say so precisely. Under the natural order the first constraint row is reached at position 4 of 28, and a two-by-two block is taken at step 3 — immediately, because there is nothing else to do with a row that has no diagonal. Under the sparsest-available order the first constraint row is reached at position 15, and the first block is taken at step 17.

Drawn, the two rows of marks are the argument. The natural order’s constraint rows are clustered at the left, mixed into a region where nothing has been eliminated yet, and its single block sits among them. The sparsest order’s are spread across the second half, each one reached after the interior around it has gone.

The distinction is between a rule that is robust to the difficulty and one that outlives it, and only the second is available here. A sparsity rule has no idea that the constraint rows are special — it is counting degrees, and a degree is a count of nonzeros. That it produces the right behaviour is a coincidence of this family’s structure, and the coincidence is not a small one: the rows with no diagonal are exactly the rows whose degree stays low longest, because their neighbours are spread through the interior rather than adjacent to each other.

By then the interior elimination has put a Schur complement into the constraint block, the diagonal entries there are ordinary numbers, and most of them pass the test alone.

So the two objectives are not aligned by luck. Sparsity and stability point the same way here because the thing that makes the matrix hard is concentrated in the rows a sparsity rule eliminates last, and it stops being hard by the time they are reached. Nothing about that is true of the unsymmetric conflict grid, where the tiny corner entry is tiny at every step and eliminating around it does not improve it.

What the blocks cost #

The two-by-two pivots are the part a reader would expect to be expensive, since a block couples two rows and two columns of the factor where a single pivot couples one.

Swept over the test’s constant, the sparsest order takes 0, 0, 1, 3 and 3 blocks as the constant rises from a tenth to nineteen twentieths, and its factor holds 70, 70, 72, 74 and 74 entries.

Each block costs about 1.33 entries.

What they buy is the growth: 4.16 at the loosest setting where no block is taken, and 1.28 once the test is strict enough to take three. A factor of three and a quarter in the growth for four entries in the factor.

That is a much better exchange rate than anything in the unsymmetric case, and the asymmetry is worth naming. In an unsymmetric elimination the price of stability is paid in fill, because a numerically acceptable pivot is usually in a denser row. In a symmetric indefinite one it is paid in blocks, and blocks are nearly free. The freedom the symmetric case lacks is compensated by a currency the unsymmetric case has no equivalent of.

It is also worth noticing what the loose settings are doing. At a constant of a tenth the factorisation takes no blocks at all and still completes — the zero diagonals have filled in by the time it reaches them, so a one-by-one pivot is available, and it is merely a poor one. The blocks are not what makes the factorisation possible on this matrix; they are what makes it accurate.

What a strict test costs when it has nothing to gain #

The sweep runs the test’s constant from a tenth to nineteen twentieths, and the two ends of it are worth separating because only one of them is a real setting.

A constant of a tenth accepts almost any diagonal entry alone. On this matrix that means the factorisation reaches the constraint rows, finds the Schur complement’s diagonal entries sitting there, accepts them however small they are, and takes no blocks at all. It completes, it reproduces the matrix to within rounding, and its growth is 4.16.

A constant of nineteen twentieths accepts a diagonal entry only when it is nearly the largest thing in its column. It takes three blocks and its growth is 1.28.

Between those, the factor’s size moves from 70 entries to 74. The whole range of the test — from almost never blocking to almost always — is worth four entries, where the choice of ordering is worth forty-three.

That is an unusual shape for a stability knob and it says something about how to set one. The usual reason to leave a pivot test loose is that tightening it costs fill, and on this family it does not: tightening it costs almost nothing and buys a factor of three. So the classical constant, which was derived by balancing the growth of a block against two successive single pivots rather than by pricing fill, turns out to be conservative in the currency it was not derived in.

It is worth being careful about what that licenses. The four entries are four entries on this matrix, where the blocks are between rows that were going to be coupled anyway. On a matrix whose blocks straddle rows far apart in the ordering, a block would couple two distant parts of the factor and could be expensive — and nothing here measures one.

What the whole of both essays says about a pivot rule #

The two families now measured say something neither says alone, and it is about which currency a rule spends.

An unsymmetric rule chooses a row and a column, and the two objectives genuinely conflict: the conflict grid is built so that they must, and the column rule’s whole value is that it can step sideways to a different column and pay in fill for what it gains in growth. That trade is real and the search width is how much of it a code can afford.

A symmetric rule cannot step sideways. What it can do instead is wait, and it turns out that waiting is what a sparsity rule already does. So the symmetric case has less freedom and needs less, and the blocks that replace the freedom cost about one entry each.

The practical consequence is a short piece of advice with an unusual shape. For an unsymmetric sparse factorisation, the ordering and the numerical pivoting have to be decided together, which is an ordering that does not wait for the numbers’s subject. For a symmetric indefinite one on this family, they can be decided separately: choose the ordering for fill, run the pivot test strictly, and accept the blocks it asks for. That separation is exactly what a quasi-definite matrix has by theorem rather than by measurement — the order decides the memory establishes what an ordering is worth in the first place, and the quasi-definite case is where any symmetric permutation is legal and the numeric phase is forbidden to move a pivot at all.

What must fail for any of this to be wrong #

Six claims and a refusal. That the constraint block has no diagonal entry to begin with, at every constraint row. That the factorisation reproduces the permuted matrix at every size, constant and order measured — the claim the rest rests on, and the one a hand-written block factorisation most easily fails, since a two-by-two update carries a two-by-two inverse whose sign can be wrong in a way that produces a stable and plausible factorisation of a different matrix. That the sparsest order holds under four fifths of the natural order’s entries at every constraint density. That it does not pay for it in growth. That a stricter test takes more blocks and lowers the growth by more than half. And that each block costs fewer than four entries, so the whole cost of the blocks is small beside what the ordering decides.

The refusal is fed the claim that the sparser ordering pays in growth, as it does without symmetry, and required to fail.

The residual is measured against the permuted matrix rather than the original, which is the only form the claim can take: the factorisation returns a permutation along with the factor, and a residual computed against the unpermuted matrix would be measuring the permutation rather than the arithmetic.

What this does not settle #

One family. A saddle-point matrix with a tridiagonal interior and a few short constraint rows is the shape this collection’s other essays on the subject use, and it is a narrow slice of what a symmetric indefinite matrix can be. It is the same family what survives one step of the barrier works on, where the interior operator changes at every outer iteration and the constraint block does not. A matrix whose difficulty is spread over the whole diagonal rather than concentrated in a block would not have the property the mechanism above depends on.

The ordering is recomputed at every step from the current degrees, which is the exact rule and not the one a code runs. A real symmetric code computes an ordering once from the pattern and then permutes inside it, which is precisely the reuse the order that was right last time prices for the unsymmetric case — and the whole finding here depends on the ordering responding to what the elimination has already done.

And the growth factor is measured and the backward error is not. A small growth factor is the standard proxy for backward stability and it is a proxy: the bound it enters has a dimension factor in front of it, and on a matrix with a two-by-two pivot the constant is not the same constant. The gap between a growth factor and a backward error is measured directly in a threshold between fill and growth, where the threshold is swept and both are reported.

Still open: an ordering computed once, and where the difficulty is spread #

The static ordering, which is what a code runs. Everything above recomputes the degrees at every step. A production symmetric code computes a fill-reducing permutation from the pattern alone, before any number is read, and then does its pivoting inside that permutation. If the mechanism here is deferral, a static ordering should keep most of the benefit — a minimum-degree permutation of this matrix also puts the constraint rows late — and the measurement that would say so is the same sweep with the ordering fixed in advance. It would also say what the symbolic phase can promise, which is the question a code actually asks.

A matrix whose difficulty is not concentrated. The mechanism is that the rows with no diagonal are the rows a sparsity rule eliminates last, and they stop being difficult in the meantime. A symmetric indefinite matrix with small diagonal entries scattered through it — rather than a zero block at one end — has the same shortage of pivots and no place to defer it to. Whether the sparsest order still wins there, or whether the conflict finally appears, is the direct test of the explanation.

The two-by-two pivots’ real price. A block costs 1.33 entries in the factor and that is a count of stored numbers. Applying a block pivot in a solve is a two-by-two system rather than a division, and in a sparse code it is also a different loop with a different memory pattern. Whether the arithmetic price matches the storage price — the question a second objective that is the first one doubled answers for a hierarchical product, where the two turn out to be the same measurement — is not answered here.

And the constant as a tunable rather than a constant. Bunch and Kaufman’s value balances the growth of a block against two successive single pivots, and it is derived rather than fitted. The sweep here shows the factor’s size barely moving across it while the growth falls by a factor of three, which suggests the classical value is conservative in fill terms and could be raised. What raising it costs on a family where the blocks are not nearly free is the measurement that would say whether the constant deserves to be a constant.