Three eigenvalues, and two are the golden ratio

Almost every claim about a preconditioner on this site is a measurement. Incomplete Cholesky does something to a spectrum that nobody can write down; a multigrid V-cycle’s convergence factor is 0.1002, measured, against a bound that is loose; an aggregation fails at 45° for reasons that took a figure to find. Preconditioning is where the subject stops having theorems.

The saddle-point matrix has one, and it is unusually sharp.

The statement #

Take K = [[H, Aᵀ], [A, 0]] with H positive definite and A of full row rank, let S = AH⁻¹Aᵀ be the Schur complement the previous essay formed, and precondition with

P = [ H 0 ] [ 0 S ]

which is symmetric positive definite because both blocks are. Then P⁻¹K has exactly three distinct eigenvalues:

1 with multiplicity n − m (1 + √5)/2 with multiplicity m (1 − √5)/2 with multiplicity m

That is Murphy, Golub and Wathen’s result. The two irrational values are φ = 1.6180339887… and 1 − φ = −0.6180339887…, the golden ratio and its conjugate, and they arrive from λ² − λ − 1 = 0 rather than from anything anybody put there.

The derivation takes four lines. Let (u, v) be an eigenvector with eigenvalue λ. The block equations are Hu + Aᵀv = λHu and Au = λSv. If λ ≠ 1, the first gives u = (λ − 1)⁻¹H⁻¹Aᵀv, and substituting into the second gives (λ − 1)⁻¹Sv = λSv, so λ(λ − 1) = 1 — which is λ² − λ − 1 = 0. The other n − m eigenvalues have v = 0 and λ = 1. Nothing about the matrices survives into the answer except their shapes.

Which means three steps #

A matrix whose minimal polynomial has degree three is annihilated by (M − I)(M² − M − I), a cubic. A Krylov method builds its iterate from a polynomial in the matrix applied to the residual, so a polynomial of degree three can make the residual zero exactly, and any optimal Krylov method therefore terminates at step three — in exact arithmetic, at every size, every conditioning and every seed.

Because P is positive definite, the method available is MINRES on the symmetrically preconditioned system L⁻¹KL⁻ᵀ with P = LLᵀ, which has the same eigenvalues and is symmetric, so the three-term recurrence is legal. The essay that introduced MINRES is about why conjugate gradients cannot be used here at all: CG divides by pᵀKp, which is a curvature, and an indefinite matrix supplies zero and negative ones. That distinction is upstream of everything on this page.

Where the golden ratio comes from, which is not numerology #

It is worth stating plainly, because a number with a name in it invites suspicion.

Nothing in the derivation is about H or A or their sizes. The quadratic λ² − λ − 1 = 0 comes from composing two operations: the first block row converts a multiplier into a displacement by dividing by (λ − 1), and the second converts a displacement back into a multiplier by multiplying by λ. Requiring the round trip to be the identity is λ·(λ − 1)⁻¹ = 1, and the golden ratio is the number whose reciprocal is itself minus one. That is the definition of φ, and it is why it appears here and not, say, √2.

So the constant is a property of the block structure — a 2 × 2 arrangement in which one block is the identity after preconditioning and the other is the zero the problem supplied. Change the arrangement and the constant changes with it. Regularise the (2, 2) block by −γS and the quadratic becomes λ² − (1 − γ)λ − 1, whose roots move continuously away from φ and 1 − φ; scale the preconditioner’s second block by a factor α and they move again. Neither is a different theorem, and both are why this page’s assertion checks the values against the closed form rather than checking that there are three of them.

What three steps actually reach, which is not zero #

In floating point the residual after three steps is not zero, and what it is instead is the measurement worth having. Across eight decades of κ(H) and three problem shapes:

κ(H) = 1 residual after three steps 1.05·10⁻¹³ to 1.96·10⁻¹¹ κ(H) = 10⁴ 2.04·10⁻¹⁰ to 5.25·10⁻¹⁰ κ(H) = 10⁸ 7.20·10⁻¹⁰ to 1.11·10⁻⁹

The floor rises with κ(H), and by far less than κ(H) does: six orders of floor against eight orders of conditioning. And the same eight decades move the computed golden ratio from agreeing with its closed form to fifteen digits to agreeing to eight. Both of those are the arithmetic charging for a conditioning the algebra does not notice, and both are reported rather than tuned away.

The comparison that says what the three steps were worth is the same system without the preconditioner, to the same tolerance: between 3 and 46 iterations across the same cases. The three at the bottom of that range is the control — at κ(H) = 1 the block H is the identity, K already has few enough distinct eigenvalues to finish in three unaided, and the preconditioner is not what makes it possible there. At every other stop it is.

The preconditioner nobody can afford #

Building P means building S = AH⁻¹Aᵀ, which costs m solves with H and a factorisation of the result — and having done that, the range-space method would have solved the system outright with no iteration at all. So the exact block-diagonal preconditioner is never used, and a page that stopped here would have proved a theorem about a method nobody runs.

Its use is different and it is the reason this essay exists: it is the statement the affordable preconditioners are measured against. Replace S by something cheap and the three eigenvalues become three clusters. How tight the clusters are is how good the approximation is — and that is a quantity computable without a reference solution, because the target is 1, φ and 1 − φ whatever the problem is.

That is rare. Most of this site’s diagnostics for an approximation require knowing the answer: the drift a factorisation has accumulated, the accuracy an incomplete factorisation gives up, what a truncation cost. Here the target is three numbers that were known before the matrix existed.

Two cheap approximations, priced #

The library implements two, and both are the sort a sparse code would actually reach for.

A diag(H)⁻¹Aᵀ needs no solve with H at all — only its diagonal — so it costs one sparse triple product. On a twelve-by-five problem with κ(H) = 100 it spreads the spectrum by 2.66 from the closed form and takes the iteration count from 3 to 11.

A scaled AAᵀ, which throws away H entirely and keeps only its average diagonal entry, spreads it by 3.04 and takes 11 as well. The two land at the same count here, and the spread orders them correctly — which is the point of having a diagnostic that does not need a reference: the spread separates the two approximations where the iteration count does not.

The refusal this page publishes is the reading that would let the theorem be quoted about those: that a block-diagonal preconditioner gives three eigenvalues, so a reasonable approximation gives three too. The assertion is fed the diagonal approximation and required to reject the claim, and it does. The three values are a property of the exact Schur complement and of nothing else.

The two ways a preconditioner can work, and this is the second #

The iterative field’s preconditioners all work the same way: they reduce a condition number, and the rate improves because the rate is governed by κ. Incomplete Cholesky takes κ from 10⁶ to 10³ and the iteration count falls by the square root of the ratio, as the bound says it should.

This one does not reduce a condition number in any useful sense. It replaces a spectrum spread over two intervals by a spectrum concentrated at three points, and what the Krylov method exploits is not the narrowness of the intervals but the finiteness of the set. A polynomial can be made to vanish at three points exactly; it can only be made small on an interval.

That distinction is worth carrying, because it says what to aim an approximate preconditioner at. Aiming at a smaller condition number and aiming at fewer clusters are different objectives, and on a saddle-point system the second is the one that pays. A preconditioner that halves κ and leaves the spectrum smeared is worth less than one that leaves κ alone and pulls the eigenvalues into three tight groups — and the second is what a good approximate Schur complement does.

Why the spread is the right diagnostic and the condition number is not #

A tempting alternative is to report the condition number of the preconditioned matrix, which is what any other field here would do. It is the wrong number twice over.

An indefinite matrix’s κ₂ is the ratio of the largest |λ| to the smallest, and for the exact preconditioner that is φ/(φ − 1) = φ² = 2.618. A preconditioned matrix with κ = 2.618 sounds excellent and says nothing about the three steps: a definite matrix with κ = 2.618 would take several iterations to reach 10⁻¹⁰, and this one takes three because of where the eigenvalues sit rather than how far apart they are.

And for an approximate preconditioner κ₂ can be small while the spectrum is a mess — three clusters straddling zero, none of them tight — which is the case a Chebyshev bound handles badly and a Krylov method handles by finding a polynomial that is small on all three. The number of clusters and their widths is what governs the count. The spread from {1 − φ, 1, φ} measures exactly that, and it is available at the cost of one eigendecomposition of a small matrix.

What it costs to check the theorem at all #

The three eigenvalues are a statement about P⁻¹K, and P⁻¹K is not symmetric. Forming it and handing it to a general eigensolver would work — the Francis algorithm is in the library and the next essay uses it — but it would measure the theorem through a routine whose own accuracy on a non-symmetric matrix is a separate subject with its own failures.

The symmetric route avoids that entirely. P is positive definite, so P = LLᵀ exists; L⁻¹KL⁻ᵀ is symmetric and similar to P⁻¹K, because L⁻ᵀ(L⁻¹KL⁻ᵀ)Lᵀ = L⁻ᵀL⁻¹K = P⁻¹K. So the spectrum can be taken by a Jacobi sweep on a symmetric matrix, where every eigenvalue is well conditioned and the answer is accurate to the rounding level relative to the norm.

That is also what makes preconditioned MINRES legal: the method needs a symmetric operator, and L⁻¹KL⁻ᵀ is the symmetric operator the preconditioned iteration is implicitly run on. In practice no code forms L or the transformed matrix — the standard implementation applies P⁻¹ once per step and keeps two inner products — but the analysis and the figure both go through the transformation, and it is the reason the preconditioner has to be definite rather than merely invertible. The next essay’s preconditioner is not, and pays for it.

What the theorem does not survive #

Three hypotheses, and dropping any of them loses the result.

H must be positive definite, or P is not a legal preconditioner for MINRES and the symmetric preconditioning L⁻¹KL⁻ᵀ does not exist. This is the same hypothesis the range-space method needs, and it fails in the same problems.

A must have full row rank, or S is singular and P is not invertible. A dependent constraint row breaks this page as thoroughly as it breaks the inertia claim.

The (2, 2) block must be exactly zero. Regularise it — as the sixth essay in this field does for an entirely different reason — and the derivation’s second block equation gains a term, the quadratic gains a coefficient, and the roots move off φ. They move continuously, so a small regularisation gives a small spread, and that is measurable in exactly the same way as the two approximations above.

The library’s other two refusals cover the parts of this that a reader is most likely to get backwards. One is fed the claim that the unit eigenvalues are exactly one in floating point and required to refuse it. The other is fed the claim that the constraint preconditioner of the next essay is positive definite, and required to refuse that too: it has the same zero block as K and therefore the same inertia, which is why it needs a different iteration.

Two routes to the same list #

The spectrum on this page is computed twice, by routes that share nothing.

The first is a symmetric eigendecomposition of L⁻¹KL⁻ᵀ, formed by a Cholesky of P and two triangular solves. It is O((n + m)³), it goes through a Jacobi sweep, and its answer is a list of floats.

The second is a pencil of nothing: the closed form, three numbers, written down from the block structure. The comparison is the agreement between them, and the figure reports the worst distance anywhere — 10⁻¹⁵ at κ(H) = 1 and 2.2·10⁻⁸ at κ(H) = 10⁸.

That second number is the interesting one, and it is what a page proving a theorem should be careful to report. The theorem is exact. The computation of the thing the theorem is about is not, and the amount by which it is not tracks the conditioning of a block the theorem never mentions. A reader who takes away “the eigenvalues are 1, φ and 1 − φ” has the algebra; a reader who takes away “and they are computed to eight digits at κ(H) = 10⁸” has what the machine will actually hand back.

At other settings #