An eigenvalue one vector cannot see

Take a symmetric matrix with an eigenvalue of multiplicity two, hand it to the best Krylov eigensolver available, and run it until the Krylov space is nearly the whole space. It returns the eigenvalue to fifteen digits. It returns it once, and reports nothing at all about the fact that its eigenspace is a plane.

That is not a convergence failure, a rounding artefact or a defect in anybody’s implementation. It is a property of the space the method works in, it cannot be repaired by running longer, and it is repaired completely by starting from two vectors instead of one.

Why it happens, in three lines #

The Krylov space of a vector v is

K_m(A, v)  =  span{ v, Av, A²v, …, A^{m−1}v }

Write v in an eigenbasis: v = Σ cᵢ xᵢ. Then Aᵏv = Σ cᵢ λᵢᵏ xᵢ, so every vector in the Krylov space is a combination of the xᵢ with weights that depend only on the λᵢ — and two eigenvectors sharing an eigenvalue are weighted identically at every power.

So if λ is doubled, with eigenvectors x₁ and x₂, the whole Krylov space meets that eigenspace in the single direction c₁x₁ + c₂x₂ — the one v happened to have a component along. No power of A can separate the two, because A does not distinguish them.

That is the same fact the depth phase’s subspace essay states from the other side: a double eigenvalue has no eigenvector for an algorithm to get wrong, because any vector in the plane is an eigenvector and the individual eigenvectors are not defined. Here the same degeneracy costs a method something rather than excusing it.

The measurement, and the size of the space #

The last row is the one that settles it. Twenty-three dimensions out of twenty-four: the space contains almost everything, the recurrence has terminated because there is nothing left to add, and the answer is still one copy.

A block of two starting vectors, run for twelve block steps — a space of dimension 22, smaller than the single-vector space in the last row — returns two copies, both accurate to 10⁻⁹.

The counting rule for “copies” is the ghosts detector read in the opposite direction, and that is worth being explicit about. There, two Ritz values converged on one eigenvalue was a defect: a duplicate produced by lost orthogonality, an eigenvalue reported twice by a method that had forgotten it had already found it. Here, with orthogonality kept throughout, two Ritz values on one eigenvalue is the only way a repeated eigenvalue can be represented at all. Same measurement, opposite verdicts, and what separates them is whether the eigenvalue is repeated in A.

The near-degenerate case, where nothing is impossible and everything is slow #

Exact multiplicity is a measure-zero situation, and a reasonable objection is that no measured matrix has one. So put the two eigenvalues a stated distance apart and let the gap close.

Two readings, and the second is the honest one.

The single-vector cost grows as the gap closes and the block’s does not. That is the standard claim for block methods and it is visible here: 17 → 22 against 11 → 11.

And the block does not save arithmetic. A block step costs two products with A, so the block spends 22 products where the single vector spends 17 to 22. At the closest gap they are exactly level. The saving is entirely in the number of iterations, and that is asserted alongside the claim rather than left out of it, because leaving it out is how a block method acquires a reputation for being faster than it is.

On this site that distinction has a field of its own. The cost field exists because a count of arithmetic stopped predicting anything thirty years ago, and the message and the word counts the other thing a machine charges for: how many times the processors have to stop and talk. An iteration of a Krylov method is a synchronisation whether or not it is a flop, so halving the iterations at constant arithmetic is a real saving in the only currency that has been scarce for a while — and it is invisible to every operation count.

What a block actually costs #

Three things, and none of them is arithmetic.

Storage. A block of b vectors is b vectors per step rather than one, so the memory for m steps is b·m. On a problem where the single-vector method already needs restarting, the block one needs it sooner.

A QR at every step. The block has to be orthonormalised before it is used, which is a Householder QR of an n×b matrix per step — this site’s own, so the orthogonality is the quantity the orthogonality field measures rather than an assumption.

And a decision about b. Two is right for a double eigenvalue and wrong for a triple one, and a block of four on a matrix with simple eigenvalues spends four times the arithmetic to find them in a quarter the iterations, which may or may not be the trade wanted. There is no way to read the right b off the matrix in advance: it is the multiplicity, and the multiplicity is the thing being computed.

That last one is a genuinely awkward circularity and it is the practical reason blocks are used cautiously. What is not awkward is the diagnosis: a single-vector run that returns one copy of an eigenvalue says nothing about whether the eigenvalue is simple, and re-running with b = 2 answers that in one experiment.

What the site’s own machinery had to be checked against #

The restart machinery writes the Lanczos recurrence out a second time, because it has to start from a given vector and the site’s own lanczos starts from a seeded random one. A second implementation of a routine the site already has is exactly the kind of thing the fleet’s duplication gate is suspicious of, and correctly so.

So it is held against lanczos.js on the one input where the two must agree — the same matrix, the same starting vector, the same number of steps — and the Ritz values agree to 5.3·10⁻¹⁵. Without that, every number in this essay could be measuring a bug in a copy.

The block recurrence is a third implementation and cannot be checked that way, since the site has no other block method. What it is checked against instead is the single-vector one at b = 1: the same code path, one column wide, must reproduce the ordinary recurrence — and the finding that a single vector returns one copy is measured through the block code at b = 1, so a mistake that made blocks work would have to also make b = 1 fail.

Where this leaves the eigenvalue field #

The spectra field has now measured four separate things a symmetric eigensolver cannot do, and they are different in kind, which is worth laying beside each other:

• an eigenvalue can be ill conditioned — the unsymmetric case, where a perturbation at the level of storing the matrix moves the spectrum by 10⁻²;
• an eigenvector can be ill conditioned while its eigenvalue is not — the gap decides it, and the plane the two span is perfectly well behaved;
• an eigenvector can fail to exist — the exactly repeated case, where the individual vectors are not defined and only the subspace is;
• and now: an eigenvalue can be invisible to a method — not badly conditioned, not hard to approximate, simply absent from the space the method searches.

The fourth is the only one that is a property of the algorithm rather than of the matrix, and it is the only one with a complete fix.

What the block costs, in the currency the site already counts #

The measurement above is about what a space contains. What it costs to enlarge the space is a separate question, and it is worth putting in the same units the cost field uses rather than leaving it as “more work”.

Storage is b vectors per step rather than one, so a run of m steps holds b·m. On a problem where the single-vector method already needs restarting, the block one needs restarting sooner, and the two mechanisms have to be combined — which is what real codes do and what nothing here draws.

Arithmetic is b products with A per step, so at equal iterations the block does b times the work. The gap table above is the case where that is exactly offset: 11 iterations at two products each against 17 to 22 at one, which is a wash in flops and a halving in iterations.

And an orthonormalisation per step. The block has to be made orthonormal before it is used, which is a Householder QR of an n×b matrix at every step — this site’s own, so the orthogonality is ‖QᵀQ − I‖ rather than an assumption. That is a small cost at b = 2 and it is the term that grows quadratically in the block width, which is one reason blocks in practice are narrow.

Choosing the block width, which is the awkward part #

Two is right for a double eigenvalue and wrong for a triple one. Four on a matrix with simple eigenvalues spends four times the arithmetic to reach the same answers in a quarter of the iterations, which may or may not be the trade wanted.

There is no way to read the right width off the matrix in advance, because it is the multiplicity and the multiplicity is what is being computed. That circularity is genuine and it is the practical reason blocks are used cautiously.

What is not circular is the diagnosis. A single-vector run that returns one copy of an eigenvalue says nothing about whether the eigenvalue is simple; re-running with b = 2 answers that in one experiment, and the answer is a count rather than a judgement. So the cheap procedure is: run the single-vector method, and re-run with a block of two on any eigenvalue whose multiplicity matters.

What the field has now measured about degeneracy #

The spectra field has, by this essay, four separate statements about what happens when eigenvalues coincide or nearly do, and they are different in kind rather than in degree:

• an eigenvalue can be ill conditioned — in the unsymmetric case, where a perturbation at the level of storing the matrix moves the spectrum by 10⁻²;
• an eigenvector can be ill conditioned while its eigenvalue is not — the gap decides it, and the plane the pair spans is perfectly well behaved;
• an eigenvector can fail to exist — at exact multiplicity, where any vector in the eigenspace is an eigenvector and the individual ones are not defined;
• and an eigenvalue can be invisible to a method — not ill conditioned, not hard to approximate, simply absent from the space the method searches.

The fourth is the only one that is a property of the algorithm rather than of the matrix, and it is the only one of the four with a complete fix.

What was checked, and against what #

The single-vector and block recurrences used here are two more implementations of a recurrence this site already has, and a second body for an existing routine is the thing kit_dup_check is written to be suspicious of. Both are checked rather than trusted.

The single-vector recurrence is held against lanczos.js on the one input where the two must agree — the same matrix, the same starting vector, the same step count, full reorthogonalisation in both — and the Ritz values agree to 5.3·10⁻¹⁵.

The block recurrence cannot be checked that way, because the site has no other block method. What it is checked against instead is itself at b = 1: the same code path, one column wide, is what produces every “one copy” row in the table above. So a bug that made blocks appear to work would have to also make the width-one case appear to fail, which is the opposite of the direction a bug in a block implementation usually goes.

And the matrix is built from its spectrum, by withSpectrum, so the doubled eigenvalue is doubled exactly rather than to within an eigensolver’s tolerance. Every claim about multiplicity above is a claim about a matrix whose multiplicity was chosen, which is the only way a claim of this kind can be checked at all.

What is left #

Higher multiplicities and the right block size, which is the circularity above and has real answers in practice — adaptive blocking, and restarting with a block whose width is grown when duplicates appear.

Block methods on non-symmetric matrices, where the Arnoldi recurrence replaces the three-term one and the block structure interacts with the Schur form’s 2×2 blocks in a way nothing here touches.

And clustering rather than multiplicity. The gap table above closes a gap to 10⁻⁴ and both methods still separate the pair. Real matrices have clusters of ten or twenty eigenvalues at a spacing of 10⁻¹² — where the distinction between “repeated” and “close” is below the arithmetic’s ability to make it, and the honest object to compute is the invariant subspace rather than the individual values, which is exactly what the depth phase’s essay recommends and what nothing in this field currently returns.