An eigenvalue that arrives twice

An orthogonalisation nobody calls one builds the Arnoldi process for GMRES: a Krylov basis, built one vector at a time, orthogonalised against everything before it. Lanczos is the symmetric case of the same thing, and symmetry buys something remarkable — the orthogonalisation collapses to a three-term recurrence. Each new vector needs only the previous two, so a basis of any length costs one matrix–vector product and a handful of operations per step, and nothing has to be stored.

It is the most-used eigenvalue method there is at scale, and it is this site’s clearest case of an algorithm that fails by returning a plausible answer.

The recurrence, and what it promises #

Start from a random vector, normalise, and repeat: multiply by A, subtract the components along the previous two vectors, normalise. After m steps there is an orthonormal basis Q of the Krylov space and a symmetric tridiagonal matrix T with QᵀAQ = T.

In exact arithmetic that is a similarity on the subspace, so the eigenvalues of T — the Ritz values — approximate A’s, and they approximate the extremes first and fastest. Run m = n steps and T is orthogonally similar to A and has its spectrum exactly.

That claim is checked here before anything else. With full reorthogonalisation at m = n = 24 the tridiagonal’s spectrum agrees with the prescribed one to a worst relative error of 5.5·10⁻¹⁵, and ‖QᵀQ − I‖ is 1.6·10⁻¹⁵. If that failed, every number below would be measuring a bug rather than a phenomenon.

Without it, the basis stops being a basis #

The measurement worth having is not that orthogonality is lost — everything loses orthogonality — but the shape of the loss. Measured at n = 40:

10⁻¹⁶ … 10⁻¹³ for ten steps, then
3·10⁻¹²  5·10⁻¹¹  9·10⁻¹⁰  2·10⁻⁸  2·10⁻⁷  4·10⁻⁶  10⁻⁴  10⁻³  3·10⁻²  4·10⁻¹  1

A factor of about seventeen a step, for ten consecutive steps, twelve orders of magnitude — and then flat, at order one, because ‖QᵀQ − I‖ cannot grow once the vectors have stopped being independent.

That is not what accumulated rounding error looks like. Accumulated error grows like the square root of the step count and keeps going; this is geometric over a run and then saturates, which is the signature of a mechanism rather than of an accumulation.

The first version of this assertion looked for a single large jump, which is the shape the word “collapse” suggests. It is not what happens: the largest one-step ratio is 21.8, which a drift could plausibly produce once. The run is the signature, not the jump, and asserting the jump would have been asserting a property the data does not have while the property it does have went unchecked.

And it happens exactly when something converges #

The dashed line on that figure is the step at which the first Ritz value first reaches full accuracy against the true spectrum. Orthogonality crosses √u at step 14 and the first Ritz value converges at step 11.

That is Paige’s result, and it is what turns this from an unfortunate numerical behaviour into an explicable one. The loss of orthogonality is not random and it is not uniform: it happens in the direction of a converged Ritz vector. The recurrence, having found an eigenvector, starts losing orthogonality specifically against that eigenvector — and the component it loses grows until the next basis vector has a substantial piece of it.

Which is why the ghost is a copy rather than noise. The algorithm has effectively restarted in a direction it already explored, so it rediscovers the eigenvalue it already found, to full accuracy, as many times as the run permits.

assertTheCollapseTracksConvergence asserts the two step numbers agree to within three, which is a claim that could have come out the other way and is the only evidence here that the mechanism is the one named.

What comes back #

At n = 40, eighty steps:

Twenty-five extra copies across thirteen eigenvalues, on a matrix whose forty eigenvalues are distinct by construction. The four well-separated ones at the top — the ones Lanczos converges on first, and therefore the ones it loses orthogonality against first — arrive five times each.

And the copies are accurate. The worst relative error among them is 1.9·10⁻⁸. That is eight correct digits from a computation that has made no arithmetic error, and it is what makes them undetectable: a caller looking at the Ritz values sees five numbers agreeing to eight digits and concludes, reasonably, that an eigenvalue of multiplicity five has been found to high precision.

The counting rule is deliberately strict about this. A duplicate requires two Ritz values near the same true eigenvalue — not merely two Ritz values near each other, which is the method working when the eigenvalues are genuinely close. A lazier count would report the site’s own clustered test spectrum as full of ghosts.

It is a mechanism, not an artefact of stopping #

The distinction that makes this worth an assertion rather than a remark. A fixed set of duplicates could be an accident of where the run happened to stop. A count that grows with the run is the recurrence continuing to lose orthogonality against each newly converged Ritz vector.

Eighty steps give 25 extra copies with the largest eigenvalue arriving five times. A hundred and twenty steps give 71, with the largest arriving eight times. Running longer produces more of them rather than better versions of the same ones.

There is a second termination fact in the same measurement, and it is the sharpest single sentence in this essay. Full reorthogonalisation stops at exactly step n. Asked for eighty steps on a 40×40 matrix it takes forty and stops, because β falls below the tolerance — the Krylov space has dimension n and there is genuinely nothing left. The plain recurrence asked for eighty takes eighty, and the extra forty vectors are built entirely out of the orthogonality it has lost.

An algorithm that does not notice it has exhausted its own search space is producing output from rounding error, and continues to do so indefinitely.

The cheap repair, and why it is enough #

Full reorthogonalisation projects each new vector against every previous one. It works completely and it costs O(n²) projections and O(n²) storage, which is the whole of what the three-term recurrence was for.

Selective reorthogonalisation — Parlett and Scott’s — projects only against the converged Ritz vectors, and only when the estimate says orthogonality has decayed to √u. It works because the directions that matter are exactly the ones Paige’s theory names: orthogonality is not being lost uniformly, it is being lost against converged Ritz vectors, so repairing those repairs all of it.

Measured at n = 40, m = n:

Six times cheaper, and zero ghosts. And the basis it leaves is not orthogonal to rounding — it is at 10⁻⁷, which is √u to within a factor of seven.

That is the claim rather than a shortfall, and it is asserted in that direction. Below √u the square of the lost orthogonality is under u, and the Ritz values are then as accurate as the precision permits; nothing is bought by going further. assertTheLanczosAssertionsReject feeds the claim that the selectively reorthogonalised basis is fully orthogonal and requires it to fail — the opposite mistake to the obvious one, and the one that would make the cheap method look like the dear one.

Why the comparison runs to exactly n steps #

Worth stating because getting it wrong reverses the answer.

Run the comparison to 80 steps on a 40×40 matrix and the numbers come out 2,352 projections for selective against 820 for full — the wrong way round, by a factor of three. That is not a measurement of reorthogonalisation. It is charging the cheap method for forty steps the dear one correctly declined to take, since full reorthogonalisation stopped at step 40 and the others did not.

The Krylov space has dimension n. A comparison run past it compares a method that has finished against two that are producing vectors out of rounding error, and any cost per step is then a cost of running when there is nothing left to do.

What this says about multiplicity #

Rank is a decision establishes that a floating-point matrix does not have a rank — that a numerical rank is a decision about a gap, and the gap is worth printing beside it.

A multiplicity read off a Lanczos run is worse than a decision. It is not a threshold applied to a quantity that has a gap somewhere; it is a count of numbers the algorithm produced, and the algorithm produces as many as it is allowed to. The right number is not recoverable from the output at all: five copies of 10.0 and a genuine eigenvalue of multiplicity five are the same list of numbers.

What separates them is whether the basis was orthogonal, which is a fact about the run rather than about the answer — and it is not in the answer. Which is the whole reason assertTheGhostsAreCopies compares against a prescribed spectrum: without one, there is no way to know.

The economy that was the point #

Worth restating why anybody accepts this behaviour, because the essay so far reads as a catalogue of defects.

The three-term recurrence is what makes Lanczos usable at scale, and the economy is total. One matrix–vector product per step. Two vectors of storage. No orthogonalisation against a growing basis, so the cost per step does not grow with the step count — which is exactly what Arnoldi cannot offer, and is why the non-symmetric case is a harder engineering problem than the symmetric one despite being the same idea.

For a matrix of a million unknowns stored sparsely, that is the difference between a computation and no computation. Full reorthogonalisation gives it all back: O(m) storage becomes O(nm), and O(1) work per step becomes O(m).

So the trade is not “a correct method against a broken one”. It is a method whose cost does not grow against a method whose cost does, and selective reorthogonalisation exists because Paige’s analysis says the growing part can be restricted to the converged Ritz vectors — a set that grows far more slowly than the basis does.

The measurement in the figure is that restriction paying: 137 projections against 820, zero ghosts, and a basis at √u. The reason it is only six times cheaper here rather than a hundred is that n = 40 is a small matrix in which nearly everything converges. On a problem where forty extreme eigenvalues are wanted out of a million, the ratio is the ratio of forty to a million.

What the badge on a spectrum figure should say #

A small note about the figures, because this family departs from the site’s usual pattern.

None of the three draws a factorisation, so residualcheck does not require a residual badge, and all three carry one. ghost-ladder’s prints the extra copies with and without reorthogonalisation, the worst relative error among the copies, and how many steps the full run actually took of the number it was asked for. orthogonality-collapse’s prints the two step numbers whose agreement is the mechanism.

The site’s rule is no decomposition without its residual printed, and the habit underneath it is that the number a figure rests on belongs on the figure rather than in prose a reader may not reach. Where the two come apart — a figure with no factorisation and a load-bearing number — the habit is the one worth keeping, and a Lanczos run’s load-bearing number is ‖QᵀQ − I‖, which is the same quantity this site has printed on QR figures since its first phase.

The site’s third orthogonality loss, and the first with a different cause #

Worth putting beside the other two, because the measurement is the same and the mechanism is not.

Two Gram–Schmidts measures ‖QᵀQ − I‖ against the condition number: classical loses like κ², modified like κ, Householder flat at 1.8·10⁻¹⁵ across eleven decades. The cause is cancellation in the projection step, and it is worst when the columns are nearly dependent.

An orthogonalisation nobody calls one measures the same quantity on an Arnoldi basis inside GMRES, where the loss is again a cancellation and is again governed by how nearly dependent the Krylov vectors are.

Here the loss is governed by convergence. It has nothing to do with the conditioning of the matrix — the test spectrum is a set of well-separated integers and the matrix is perfectly conditioned — and everything to do with the algorithm having found something. A well-conditioned problem, a stable step, and a basis that falls apart on schedule.

Which is why the same measurement needed a different figure. A plot against κ would be flat and would say nothing; the plot that says something is against the step, with the convergence event marked on it. The quantity is the site’s oldest and the axis is new.

Why a random starting vector, and why one seed #

Two construction details that decide what the figures show.

The starting vector is random rather than e₁, and the matrix is VΛVᵀ for a fixed random orthogonal V rather than diagonal. Lanczos started from e₁ on a diagonal matrix converges in one step and shows nothing at all — the Krylov space is spanned immediately — so a figure drawn that way would be a figure of a degenerate case.

And there is one seed, fixed, because every figure on this site is byte-identical on every build. That is a real limitation here and it is stated rather than hidden: the step at which the first Ritz value converges depends on how much of the leading eigenvector the starting vector happened to contain, so the numbers 14 and 11 are one draw. What is not one draw is that the two events coincide, which is asserted across every size in the family gate — three sizes, each with its own run — and which is the claim the essay actually makes.

What is left #

Restarting. Nobody runs Lanczos to n steps on a large problem; the whole point is to stop early with a few extreme eigenvalues. Implicitly restarted Lanczos — the algorithm ARPACK implements and most large eigenvalue computations actually run — keeps a fixed-size basis and restarts with a filtered starting vector, and its interaction with the loss of orthogonality is a subject of its own.

Block Lanczos, which handles genuine multiplicities properly by carrying several vectors at once — and which is the actual answer to the question this essay poses, since a genuine multiplicity of five is invisible to the single-vector recurrence for a completely different reason.

And the non-symmetric case. Arnoldi has no three-term recurrence, so its orthogonalisation cost grows with the step count whether or not anything has converged, and the trade-offs are different. This site builds Arnoldi in the GMRES essay and measures its orthogonality loss there; what it does not have is the eigenvalue version, where the Ritz values are complex and the convergence theory is much weaker.