A curvature direction the factors cannot refine

Where the multipliers go measured what Bunch–Kaufman’s unbounded multipliers cost and what they do not, after a factorisation with nothing to pivot for and when symmetry is not enough had set out what a symmetric indefinite factorisation has to choose. On a 24 × 24 symmetric matrix built so that a coupling ε makes the multipliers $1.2/\varepsilon$, the solve’s backward error stayed at $1.6 \cdot 10^{-16}$ while the multipliers reached $10^{10}$: the large entries of L sit beside small pivots and cancel in every solve. What did not survive was a use of the factors that meets one without the other. A direction of negative curvature — the eigenvector of D’s most negative eigenvalue, carried back through $L^{\mathsf T}$, which is what an optimisation code reads from a factorisation to step out of a saddle — held $6.9 \cdot 10^{-16}$ of the curvature that was there at $\varepsilon = 10^{-8}$, falling as $\varepsilon^2$. The bounded rule, rook pivoting for symmetric matrices, gave a direction holding 13 per cent.

The essay then predicted the obvious repair. “A Newton-type method rarely steps along the raw direction; it takes a few iterations of a Lanczos or inverse iteration from it. The prediction with a sign is that inverse iteration with the same factors recovers the curvature within two or three steps, because each step is a solve and the solve is stable — which would make the bounded rule’s advantage a matter of the first step only.”

The direction, and three ways to refine it #

The matrix is the earlier essay’s planted family at five couplings, from $10^{-2}$ to $10^{-10}$. Its smallest eigenvalue is $-8.40$ at every coupling — the coupling lives in a corner of the matrix whose own eigenvalues are of order ε — and that number is what the curvature is measured against: a direction’s Rayleigh quotient divided by it, one for a perfect direction, zero for none, negative for a direction of positive curvature.

From each rule’s direction, three refinements are run. Inverse iteration with the same factors: solve with the factorisation, normalise, repeat — the prediction’s repair, costing one solve a step and nothing new. Power iteration on $\|A\|_1 I - A$: multiply by the matrix, shifted so that its most negative eigenvalue becomes its largest, normalise, repeat — one product with A a step. Lanczos: the same products, kept and orthogonalised, with the smallest eigenvalue of the projected tridiagonal matrix read after each one. The last two touch only the matrix; the first touches only the factors.

A solve finds the wrong end of the spectrum #

The figure at the top of the page is the direction each factorisation gives and where inverse iteration takes it. Bunch–Kaufman’s direction holds $6.9 \cdot 10^{-4}$ of the curvature at $\varepsilon = 10^{-2}$ and $6.9 \cdot 10^{-20}$ at $10^{-10}$, the $\varepsilon^2$ fall the earlier essay found. The bounded rule’s holds 0.140 at every coupling.

One step of inverse iteration with the factors leaves both directions with under a thousandth of the curvature, at every coupling: Bunch–Kaufman’s quotient becomes $-1.5 \cdot 10^{-5}$ of the smallest eigenvalue at $\varepsilon = 10^{-2}$ and $-1.5 \cdot 10^{-17}$ at $10^{-8}$; the bounded rule’s, which had a seventh of the curvature, becomes $3.7 \cdot 10^{-5}$ and $3.7 \cdot 10^{-17}$. A second step puts both on the same vector, and every later step leaves them there. Its quotient is the eigenvalue of the matrix nearest zero — $1.27 \cdot 10^{-4}$ at $\varepsilon = 10^{-2}$, $1.28 \cdot 10^{-8}$ at $10^{-4}$, falling as $1.27\,\varepsilon^2$ until it reaches the rounding level — and it is positive. The refinement does not merely fail to find the negative curvature. It finds positive curvature and stays on it.

That is not a property of Bunch–Kaufman or of the planted family; it is what inverse iteration does. A solve with A multiplies every eigenvector’s component by one over its eigenvalue, so repeated solves amplify the eigenvector whose eigenvalue is smallest in magnitude, and the most negative eigenvalue is the largest in magnitude on this matrix’s negative side. Inverse iteration finds the curvature only when it is shifted — when the factorisation is of $A - \sigma I$ with σ below the most negative eigenvalue — and a shifted factorisation is a new factorisation, not the one an optimisation code already has.

The prediction reasoned from the solve’s stability, and the solve is stable: its backward error on this family is at the rounding level for both rules. Stability says the solve computes $A^{-1}x$ accurately. It says nothing about whether $A^{-1}x$ points anywhere useful, and on a matrix with an eigenvalue of order $\varepsilon^2$ it points at that eigenvalue’s eigenvector with a gain of $1/\varepsilon^2$.

The matrix recovers what the factors cannot #

The two refinements that use the matrix both work, and they differ in what they need from the start. At $\varepsilon = 10^{-8}$, Lanczos from Bunch–Kaufman’s direction — which holds $6.9 \cdot 10^{-16}$ of the curvature — reaches ninety per cent after seven products and ninety-nine after nine. From the bounded rule’s direction it reaches them after four and six. Turn the dial: the numbers do not move. At every coupling from $10^{-2}$ to $10^{-10}$, Lanczos needs nine products from one start and six from the other.

Power iteration needs more from the start. From the bounded rule’s direction it reaches ninety per cent of the curvature in thirteen products at every coupling. From Bunch–Kaufman’s it needs 28 at $\varepsilon = 10^{-2}$, 39 at $10^{-4}$, 54 at $10^{-6}$, and at $10^{-8}$ and $10^{-10}$ it has not reached a tenth after sixty; the dial’s last stops show its curve climbing a decade every few steps from fifteen decades down.

The difference between the two is a difference in what they do with a small component. Power iteration multiplies each eigenvector’s component by its eigenvalue of the shifted matrix, a fixed ratio a step, and so climbs from a small start at a fixed number of steps per decade: Bunch–Kaufman’s start has a component along the curvature direction of order ε, and each two decades of ε cost power iteration eleven to fifteen more steps. Lanczos keeps every product it has computed and extracts the best combination of them. It needs the start to have some component along the curvature direction, not a large one, and a product with A supplies more. From Bunch–Kaufman’s direction at $\varepsilon = 10^{-8}$, the smallest Ritz value is nothing after one product, 6.4 per cent of the curvature after two and 52 per cent after three: the vectors $Ad$ and $A^2d$ carry the direction out of the corner where it started, and Lanczos uses them the moment they exist.

So the bounded rule’s advantage survives refinement in one of the two refinements that work. Under Lanczos it is three products — nine against six, at every coupling. Under power iteration it is the difference between thirteen products and never. And under the refinement the earlier essay predicted would erase it, both rules end in the same wrong place.

The control says the same #

The planted family is built to make Bunch–Kaufman’s direction useless; a random symmetric matrix is not. On thirty of them, with standard normal entries, the factors’ direction is a modest one for both rules — a median of 0.077 of the curvature from Bunch–Kaufman’s factors and 0.103 from the bounded rule’s, since the most negative eigenvalue of D is only loosely related to the most negative eigenvalue of A when the pivoting has mixed rows. Eight steps of inverse iteration with the factors take those medians to 0.000 and 0.006: on all sixty factorisations the quotient after eight steps is under half the curvature, and on most it is a few thousandths. The eigenvalue nearest zero of a random matrix is almost never its most negative one, so inverse iteration almost never finds it. Eight Lanczos products from the same directions reach a median of 0.996 for both rules, and at least 0.749 on every one of the sixty. The control rules out the reading that the failure belongs to the planted family’s ε corner: there is no corner on a random matrix, and the solve still goes to the wrong end of the spectrum.

A shift the factors can supply #

Inverse iteration works when it is shifted, and a code with a factorisation in hand has a candidate shift without computing anything: the most negative eigenvalue of D. Sylvester’s law of inertia says D has as many negative eigenvalues as A, which is how an eigenvalue count that cannot be slightly wrong counts eigenvalues below a shift. It does not say D’s eigenvalues are A’s, and the measurement is what the difference does to a second factorisation shifted at D’s most negative pivot.

Bunch–Kaufman’s most negative pivot is $-7.34$; the bounded rule’s is $-5.44$. Neither is the smallest eigenvalue, $-8.40$, and shifted inverse iteration does what every inverse iteration does: it converges to the eigenvalue nearest its shift. From Bunch–Kaufman’s shift that is $-7.14$, the second most negative, and the quotient settles at 0.849 of the curvature. From the bounded rule’s it is $-5.02$, and the quotient settles at 0.597. Push each shift a tenth further down and Bunch–Kaufman’s, at $-8.07$, now lies nearest the smallest eigenvalue and reaches it — 0.995 after seven steps and 1.000 after eight from a start holding $10^{-16}$ of it. The bounded rule’s, pushed to $-5.98$, is still nearest $-5.02$ and stays at 0.598.

So on the one refinement that uses the factors and works, the comparison between the rules reverses. The bounded rule’s direction was the better start, and its D is the worse source of a shift: by bounding the multipliers it took a pivot sequence whose most negative pivot sits further from the bottom of the spectrum. Neither rule’s pivots promise anything about where the most negative eigenvalue is — the most negative pivot is an eigenvalue of a two-by-two block of a Schur complement, related to A’s spectrum only through the inertia count — and a shift read from them is a guess that one rule’s arithmetic happened to make well here. A code that wants a shifted factorisation would do better to take its shift from a few Lanczos products, which on this family reach the bottom of the spectrum in six to nine.

What an optimisation code should do with a factorisation’s curvature direction #

A code that has factored a symmetric indefinite matrix — a Hessian at a saddle, a saddle-point system’s reduced matrix — has two cheap things in hand: the factorisation and products with the matrix itself. The measurements say which to spend on the curvature direction.

Do not refine it with the factors. Inverse iteration with the factorisation one already has converges to the eigenvalue nearest zero, and on any matrix where that eigenvalue is not the most negative one — on every random matrix measured here, and by construction on the planted family — it destroys whatever curvature the direction had. A shifted inverse iteration would work and needs a factorisation of $A - \sigma I$, which costs what the first factorisation cost.

Refine it with Lanczos. A handful of products with A — six to nine here, eight on the random matrices — recovers the curvature from either rule’s direction, at every coupling, including from a direction that held $10^{-16}$ of it. The factorisation’s direction is worth having as a start, and almost worthless as an answer.

The cost is worth putting beside the factorisation’s. For a dense matrix a product with A is $2n^2$ operations and an LDLᵀ factorisation about $n^3/3$, so nine products cost what one factorisation does at $n = 54$, a sixth of one at $n = 324$, and a vanishing share above that; for a sparse matrix the product is cheaper still and the factorisation usually is not. A shifted second factorisation, the other refinement that works, costs a whole factorisation and needs a shift the first one cannot be trusted to supply. On every count, the products are the cheap way to a curvature direction a factorisation got wrong.

The bounded rule still matters for the cheap refinements. Power iteration, the refinement that needs nothing but a product and a normalisation and keeps nothing, recovers the curvature from the bounded rule’s direction in thirteen products at every coupling and from Bunch–Kaufman’s not at all at the smallest couplings. A minimum the Hessian cannot see used the inertia of a symmetric indefinite factorisation to settle a second-order question by counting; a curvature direction is a harder thing to read off the same factors, and how it was read decides which refinements can repair it.

Why a solve is the wrong tool here, and a product the right one #

The earlier essay’s account of the curvature failure was that the direction is read from L alone, and L’s large columns point it into the corner of the matrix where the coupling lives. A solve does not escape that corner. It applies $L^{-\mathsf T} D^{-1} L^{-1}$, and on the planted family the inverse of the matrix is dominated by that same corner, where its eigenvalues are of order $\varepsilon^2$ and its inverse’s of order $1/\varepsilon^2$ — the factors and the inverse agree about where the large numbers are, because they are the same operator.

A product with A disagrees with them. The matrix’s entries are all of ordinary size, and it couples the corner to the rest of the matrix with weights of order one. Lanczos builds the Krylov space of A from the start, and an eigenvalue that arrives twice showed how quickly that space captures an extreme eigenvalue: here the most negative eigenvalue, $-8.40$, sits 1.26 below the next, $-7.14$, on a spectrum seventeen wide, and six to nine products capture it. The same Krylov space built from $A^{-1}$ — which is what inverse iteration explores, one vector at a time — captures the extreme eigenvalues of $A^{-1}$, and those are the eigenvalues of A nearest zero.

The plane survives what its vectors do not separated a computed space from the vectors that span it. Here the factors’ direction is a vector that has lost almost everything, and the space a few products with A span around it is enough to recover what was lost.

What one family and thirty matrices do not show #

One planted family, one size, five couplings, and thirty random matrices. The refinements are run without any of the safeguards a real optimisation code would add — a trust region, a check that the quotient is negative before stepping — and those would catch inverse iteration’s arrival at positive curvature without repairing it. Lanczos is run with full reorthogonalisation, which at twenty-four dimensions costs nothing and at a hundred thousand costs a great deal; without it, an eigenvalue that arrives twice is the account of what the extreme Ritz value does, and it converges anyway. And power iteration is shifted by the matrix’s 1-norm, the cheapest bound available; a tighter shift would converge faster from both starts.

Still open: a shift the factors can supply, and the coupling met late #

How often a pivot is a usable shift. On this family Bunch–Kaufman’s most negative pivot, pushed a tenth, was a usable shift and the bounded rule’s was not. 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 coupling met late. The earlier essay’s second open question stands: placed in the last rows rather than the first, the ε coupling reaches Bunch–Kaufman after twenty pivots have mixed it into the Schur complement. Whether the factors’ direction is then any better — and whether the refinements’ ordering above changes with it — is the same sweep on the reversed family.