The push a pivot needs belongs to the matrix

A curvature direction the factors cannot refine found that inverse iteration with an indefinite matrix’s own factors goes to the wrong eigenvalue. Each step multiplies by $A^{-1}$, which amplifies the eigenvector whose eigenvalue is nearest zero, and on its planted family that eigenvalue is small and positive, so two steps turned a direction of negative curvature into one of positive curvature. The repair is a second factorisation, of $A - \sigma I$, and a shift σ near the eigenvalue wanted — and the factors already hold a candidate. Their most negative pivot, the most negative eigenvalue of the block-diagonal D, is what an inertia count reads to say there is negative curvature at all. On the planted family Bunch–Kaufman’s, pushed a tenth further, sent shifted inverse iteration to the smallest eigenvalue; the bounded rule’s, pushed as far, did not.

Its last section asked whether that was the family or the rule. “On thirty random matrices the question is how often each rule’s most negative pivot lies nearer the smallest eigenvalue than the next, and whether a fixed push — a tenth, a quarter — makes it so on most of them. The prediction with a sign is that neither rule’s pivot is a reliable shift on random matrices, and that the push needed varies by a factor of two between draws.”

The first half holds. The second understates it, and the reason it does is the useful part: a pivot is not an estimate of an eigenvalue at all, and the factorisation has a way of saying how far off it is.

Thirty matrices and two pivot rules #

The matrices are the earlier essay’s control: thirty symmetric matrices of order 24 with independent standard normal entries, seeded so that each can be rebuilt. Their smallest eigenvalues lie between $-10.3$ and $-7.2$, and the gap to the second-smallest between under two and twenty-six per cent of the smallest — the spread of a random spectrum’s edge, where the shift that stops at the first right count met its curvatures too.

Each matrix is factorised as $PAP^{\mathsf T} = LDL^{\mathsf T}$ by both rules of the earlier essays — with two-by-two pivots available, which when symmetry is not enough showed an indefinite matrix can need where every diagonal entry is useless. Bunch–Kaufman chooses between a one-by-one and a two-by-two pivot by comparing the diagonal with the largest entry in its column, with the classical threshold $\alpha = (1 + \sqrt{17})/8$; the bounded rule — rook pivoting, which a pivot that searches one row and one column measured on the unsymmetric problem — searches along rows and columns until it finds an entry largest in both, and bounds the multipliers in L. The pivot read off each is D’s most negative eigenvalue. A shift σ is usable for inverse iteration towards the smallest eigenvalue $\lambda_1$ when it is nearer $\lambda_1$ than any other eigenvalue, which for a shift below $\lambda_2$ means below the midpoint $(\lambda_1 + \lambda_2)/2$.

A fixed push serves a fixed share #

The figure at the top of the page counts the matrices on which the pushed pivot is usable. Unpushed, Bunch–Kaufman’s pivot is usable on 12 of the thirty and the bounded rule’s on 5. Pushed by a tenth, 13 and 9. By a quarter, 16 and 13. By a half, 25 and 22. It takes a push of two — doubling the pivot — for 29 of the thirty under both rules, and two and a half for all of them.

So neither rule’s pivot is a reliable shift, and the planted family’s ordering of the two does not survive: there Bunch–Kaufman’s pushed pivot worked and the bounded rule’s did not, here Bunch–Kaufman’s is usable on a few more matrices at small pushes and the two are level from a push of two. No push small enough to be called a push serves most of them.

The dial shows why a fixed push cannot work. Each pivot is a dot at its own multiple of $\lambda_1$, and the push slides every dot rightwards in proportion to where it started. A dot that starts at 0.4 needs a push of two and a half to cross the midpoint; a dot that starts at 1.5 needs none, and any push moves it further past the spectrum than it was. The second eigenvalue’s ticks are scattered between 0.5 and 0.98, so the midpoint a dot has to cross moves too. The push needed is the matrix’s, and no constant matches thirty matrices.

A pivot is not an eigenvalue #

Bunch–Kaufman’s most negative pivot runs from 0.38 of the smallest eigenvalue to 1.58 times it, with a median of 0.82. On eight matrices it is more negative than every eigenvalue the matrix has. The bounded rule’s runs from 0.46 to 1.09, median 0.66, and is past the spectrum on four, never by more than nine per cent. Neither is an estimate of $\lambda_1$ with an error that can be pushed away; the first is not even on one side of it.

The reason is in what D is. $D = L^{-1} P A P^{\mathsf T} L^{-\mathsf T}$ is congruent to A, and Sylvester’s law of inertia guarantees that the two have the same number of negative, zero and positive eigenvalues. It guarantees nothing about their sizes. A congruence by a non-orthogonal L stretches and compresses, and D’s eigenvalues can lie anywhere a well-chosen stretch puts them — inside the spectrum, or beyond either end. How far L is from orthogonal is how much latitude there is, and that is where the two rules differ. Bunch–Kaufman bounds the growth in D and leaves L’s entries free, which where the multipliers go watched reach $10^{10}$ on a matrix built for it; the bounded rule keeps every multiplier under a fixed constant, and so keeps L closer to a rotation and D closer to the spectrum. On these matrices that shows as Bunch–Kaufman’s pivots spread over a range twice as wide as the bounded rule’s, and past the spectrum by up to six times as far.

So the earlier essay’s prediction was right that the push varies and wrong about how much. Over the thirty, the push that makes Bunch–Kaufman’s pivot usable runs from 0.59 to 2.27 — a factor of 3.8 — and the bounded rule’s from 0.85 to 2.01, a factor of 2.4. A push below one is not a push; it is the matrices on which the pivot overshot, where the useful thing to do with it is to pull it back.

The inertia says when to stop #

There is a shift that is always usable: anything below the whole spectrum is nearer $\lambda_1$ than anything else. And there is a cheap, exact test of whether a shift is below the spectrum. Factorise $A - \sigma I$ and count D’s negative eigenvalues; by the same law of inertia that count is the number of eigenvalues of A below σ, and it is zero exactly when σ is below $\lambda_1$. An eigenvalue count that cannot be slightly wrong measured how reliable that count is in floating point — exact, or wrong by a whole eigenvalue inside a narrow band. The factorisation of $A - \sigma I$ is needed for shifted inverse iteration anyway, so the test costs nothing extra when it passes.

The rule is then: start at the pivot, factorise $A - \sigma I$, and while the count is not zero multiply σ by 1.25 and factorise again. When the count is zero, iterate with that factorisation.

On every matrix and both rules the search stops below $\lambda_1$, and shifted inverse iteration from there converges to $\lambda_1$ to ten digits. Bunch–Kaufman’s search makes between one and six factorisations of the shifted matrix, median two; the bounded rule’s between one and five, median three. The bounded rule starts closer to the spectrum from the inside and so needs more steps to cross it, and stops closer once it has: its final shifts lie between 1.0003 and 1.22 times $\lambda_1$, median 1.10, against Bunch–Kaufman’s 1.01 to 1.58, median 1.17, which include the eight matrices where Bunch–Kaufman’s pivot was already past the spectrum and the search stopped at once, wherever the pivot happened to be.

The eight matrices on which Bunch–Kaufman’s pivot was already past the spectrum are the search’s easiest and the iteration’s hardest. The first factorisation of $A - \sigma I$ reports no negative pivot, the search stops having made one factorisation, and the shift stays wherever the pivot put it — on the worst of them 1.58 times $\lambda_1$, more than half of $\lambda_1$ again below the spectrum. A search that only ever pushes outwards cannot pull such a shift back; it was designed for pivots that fall short, and the bounded rule’s almost always do.

Where the search stops decides the rest #

A shift below the spectrum always lands on $\lambda_1$, but how fast depends on how far below. Shifted inverse iteration multiplies the error in the eigenvector by $|\lambda_1 - \sigma| / |\lambda_2 - \sigma|$ each step and the error in the Rayleigh quotient by its square, so a shift just under $\lambda_1$ is fast and one a long way under, with $\lambda_2$ close behind, is slow.

The solves follow the ratio’s prediction across a factor of thirty: from three or four solves where the ratio is under a tenth to 103 and 125 where it is above nine tenths, on the matrix whose two smallest eigenvalues are two per cent apart and whose search stopped a fifth of $\lambda_1$ below it. The medians are 19 solves for Bunch–Kaufman’s shift and 12.5 for the bounded rule’s. The bounded rule’s pivot, worse as a shift on its own, is the better start for the search, because its dots never overshoot by much; Bunch–Kaufman’s overshooting pivots are usable at once and slow afterwards.

Lanczos, with full reorthogonalisation and started from the factors’ own direction of negative curvature, reaches the same ten digits in 15 to 23 products, median 19 — and, as the earlier essay found, 99 per cent of the curvature in 5 to 15. For a dense matrix of this order, a product and a solve cost about the same, and a factorisation about eight of either; the search’s two or three factorisations plus its solves are then in Lanczos’s range and sometimes well outside it. The search is a certificate as well as a computation: when it stops, the count of zero says σ is below the spectrum, which no number of Lanczos products says.

One more factorisation, spent inside the bracket #

The search’s slow cases are slow for a reason it already knows. Its last failed factorisation had a negative count and its last one none, so $\lambda_1$ lies between the two shifts, and the final shift can be as far below $\lambda_1$ as a quarter of the previous one. Bisecting that bracket — factorising the midpoint, keeping it when its count is still zero — moves the shift towards $\lambda_1$ at the price of one factorisation a step, and each step halves the bracket.

For a dense matrix of order 24 a factorisation costs about $n/3 = 8$ solves, and with that exchange rate one bisection step is the cheapest choice under both rules. Over the thirty, Bunch–Kaufman’s search with no bisection makes 77 factorisations and 711 solves; with one step, 99 and 515 — 1,307 solve-equivalents against 1,327. The bounded rule’s goes from 88 and 523 to 114 and 285, 1,197 against 1,227. A second step is about even for Bunch–Kaufman and dearer for the bounded rule; a third is dearer for both. The totals move by a few per cent, but the worst case moves by half: the slowest matrix needs 57 solves after one step instead of 125 for Bunch–Kaufman’s shift, and 43 instead of 103 for the bounded rule’s. That is the case the ratio’s curve predicted, a shift stopped far below a crowded edge, and a single halving takes it most of the way back.

The exchange rate is the one assumption in it. A sparse matrix whose factorisation fills in costs far more than eight solves to factorise, and there the search’s own factorisations are the expensive part and bisection is not worth a step; a matrix small enough that a solve is nearly free makes it worth several. The measurement gives both prices, so the choice can be made for the matrix in hand.

What the planted family showed, and what it hid #

The planted family was built for a different question. Its coupling ε put one eigenvalue near zero, of order $\varepsilon^2$, to show where inverse iteration with the matrix’s own factors goes; the bottom of its spectrum was left alone, at $-8.40$ with the next eigenvalue at $-7.14$, a gap of fifteen per cent — the median gap of the thirty random matrices almost exactly. For the question of shifts, the planted family was a random matrix like these, and its answer was one draw: Bunch–Kaufman’s pushed pivot usable, the bounded rule’s not, which is a combination that occurs on a handful of the thirty and the reverse on a handful of others. A family built to expose one mechanism is a single sample for every other question asked of it, and a single sample cannot tell a property of a rule from a property of the matrix.

What the thirty give a solver is a rule that does not depend on the pivot’s error. A pivot is a starting point and the inertia is a stopping test. A shift that certifies a saddle used the same count to certify the absence of negative curvature after a regularisation; here it certifies a shift’s place below the spectrum, and it does it with the factorisation the next step needs anyway.

What thirty matrices do not show #

Thirty dense matrices of one order, entries independent and Gaussian, whose spectra follow the semicircle and whose edges crowd. A matrix from an optimisation problem near a saddle has one or a few negative eigenvalues standing apart from a positive bulk — closer to the planted family than to these — and on such a matrix the pivot might well be usable unpushed, as it was there. The push factor of 1.25 is a choice; a factor of two would halve the factorisations and stop further below the spectrum, trading solves for factorisations, and the measurement above prices both sides of that trade without choosing. The counts are taken from D in double precision on matrices whose eigenvalues are separated from any shift tried by far more than the band where a count can be wrong.

Still open: the coupling met late, and a shift from the search’s own last count #

The coupling met late. The earlier essay’s second question stands. Placed in the last rows rather than the first, the planted family’s small coupling reaches Bunch–Kaufman after twenty pivots have mixed it into the Schur complement. The prediction with a sign is that the factors’ direction is then no better than on the original family for either rule, and that the most negative pivot moves past the spectrum for Bunch–Kaufman but not for the bounded rule — the difference in L’s latitude above, met in a matrix built to expose it.

A positive-definite start. On a matrix that is positive definite the factorisation is Cholesky’s, there is no negative pivot and nothing to push, and a factorisation with nothing to pivot for is the account of why. The mirrored question — D’s smallest pivot as a shift towards the smallest eigenvalue of a definite matrix — has a one-sided answer the indefinite case lacks: each Cholesky pivot is the reciprocal of a diagonal entry of some trailing block’s inverse, and interlacing puts every such entry under the reciprocal of the smallest eigenvalue, so the smallest pivot can never be below the spectrum. The search would then always need at least one push. The prediction with a sign is that on thirty random definite matrices of the same order it needs a median of four pushes, more than either rule needs here, because a definite matrix’s pivots sit near its diagonal while its smallest eigenvalue sits far below it — and that the pivot is a usable shift unpushed on none of them.