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.

How far it goes #

The hero is one step count, and the ladder is the argument.

At 50, 60, 80, 100, 120 and 160 steps the extra copies number 8, 14, 25, 45, 71 and 103, spread across 4, 6, 13, 26, 40 and 40 distinct eigenvalues, with the most-copied one arriving 3, 4, 5, 7, 8 and 11 times. Three of those columns say different things.

The count grows faster than the run. Three and a fifth times the steps buys thirteen times the copies, which is about steps^2.3 — each converged Ritz vector is a new direction to lose orthogonality against, and the number of converged vectors is itself growing.

The spread saturates at forty. By a hundred and twenty steps — three times the dimension of the matrix — every one of the forty eigenvalues has at least one spurious copy, and the extra hundred and three at a hundred and sixty steps are piled on eigenvalues that already had some. There is no subset of the spectrum a caller can trust.

And the accuracy of a copy degrades once and then stops. The worst relative error among the copies runs 1.65·10⁻¹⁴, 1.49·10⁻⁸, 1.93·10⁻⁸, 1.57·10⁻⁸, 2.28·10⁻⁸ and 2.35·10⁻⁸ — a jump of six orders between fifty and sixty steps, and then flat to within a factor of 1.6 over the remaining hundred. So the ghosts do not get worse as they multiply; they arrive at a fixed accuracy of about 2·10⁻⁸, which is √u, and stay there.

That number is the one to carry. A duplicate accurate to √u is accurate enough to survive any plausible tolerance a caller would set on a spectrum, and inaccurate enough that it is not the eigenvalue. Nothing about a single Ritz value distinguishes the two, and the reorthogonalised run — which stops at step 40 because the space is exhausted — returns zero copies at every step count on the slider.

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. But it is a weaker claim than it looks, for two reasons worth separating, and the section below repairs both.

The two ways that agreement could still be a coincidence #

The check takes an absolute value. |loss − conv| ≤ 3 would pass just as happily if orthogonality collapsed three steps before anything converged — and that arrangement is not a weaker version of Paige’s account, it is a refutation of it. A recurrence cannot start losing orthogonality in the direction of a converged Ritz vector before there is one. So the check as written cannot distinguish the mechanism from its reverse.

And it is one matrix. Two step numbers agreeing on one spectrum is one coincidence away from meaning nothing.

Twenty-seven runs — three sizes, three spectra, three seeds — with the step at which the first Ritz value reaches full accuracy and the step at which ‖QᵀQ − I‖ crosses √u:

The collapse follows the convergence at all twenty-seven, by two, three or four steps. Never zero, never negative. That is the direction the mechanism requires, and it is now measured rather than admitted by an absolute value.

And neither number moves with n. This is the part that was worth the sweep. The size goes from 24 to 60 — a factor of two and a half in the run length and in the dimension of the space the recurrence is exploring — and the convergence step stays at 8, 11 and 16 for the three spectra, while the collapse stays at 12, 14 and 19. What moves both is the spectrum: top, the number of well-separated eigenvalues at the end, takes the convergence step from 8 to 16 as it goes from 2 to 8.

That is the strong form of the claim, and it is the one that separates this from the obvious alternative account. If the collapse were an accumulation of rounding — n steps of a three-term recurrence, each one rounding — it would arrive later on a larger matrix, because a larger matrix gives the recurrence more steps in which to accumulate, and sooner on a smaller one. It does neither. It arrives three steps after a Ritz value converges, wherever in the run that happens, and a matrix two and a half times the size does not buy a single extra step of orthogonality.

The essay on two Gram–Schmidts is the contrast: there the loss is an accumulation, it does depend on the size of the problem through κ, and the fix is arithmetic. Here it is not, and no amount of care in the three-term recurrence would postpone it — which is why the repair is selective reorthogonalisation against the converged directions rather than better arithmetic.

assertTheCollapseFollowsConvergenceAndIgnoresTheSize runs all twenty-seven, requires every gap to be positive, requires the convergence step to be flat in n, and requires it to move with the spectrum — because a check that only bounded the gap would pass on a mechanism that was not this one.

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 — the same move how wide the block should be prices in a different setting — 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.

The same basis, used for something else #

The Krylov basis this page builds is not only for eigenvalues. The same subspace, with the same recurrence, computes the action of any function of the matrix on a vector — and for the exponential it converges superlinearly.

And a fixed point that arrives twice #

A method returning the same answer twice is one failure. A method returning a plausible answer that is a different fixed point is another, and it is harder to see: the output is orthogonal to the last bit and is the wrong orthogonal matrix.