How wide the block should be

An eigenvalue one vector cannot see settled what a block of two is for. A Krylov space built from one starting vector meets a two-dimensional eigenspace in exactly one direction, whatever that vector is, so a single-vector method returns one copy of a doubled eigenvalue — at 12, 16, 20 and 24 steps alike, the last on a space of dimension 23 in a 24-dimensional problem. It is not slow convergence. The second copy is not in the space.

That essay used a block of two and left the obvious question: how wide should the block be in general?

The question has a clean answer and an uncomfortable corollary. The answer is exact rather than empirical — it falls out of a statement about dimensions, not out of a convergence rate — and it says the width must be at least the multiplicity. The corollary is that the multiplicity is not something the method can find out, so the one parameter that decides whether the answer is complete has to be supplied from outside the computation.

The rule #

A block of b spans b directions, and it meets an eigenspace of dimension d in min(b, d) of them. So the rule is exact rather than approximate: the block must be at least the multiplicity, and nothing above the multiplicity changes what can be found.

Steps and products with A, on a 200-dimensional problem, to return every copy of an eigenvalue repeated the stated number of times. A dash is not a slow run: the missing copies are still missing at every step count up to a basis of half the problem’s dimension.

The cheapest working width is the multiplicity itself, at every row: 19, 32, 51 and 64 products.

The cap, and why it decides the table #

That phrase — up to a basis of half the problem’s dimension — is the whole reason the table means anything, and the first version of this measurement did not have it.

A block of b after s steps spans b·s dimensions. Run it far enough and the basis is the whole space, the projected matrix is similar to A, and the Ritz values are A’s eigenvalues — all of them, including every copy, whatever the block width was. Without a cap the measurement reported that a block of three finds a quadruple eigenvalue at twenty-seven steps, which is true and is a statement about eighty-one vectors in an eighty-dimensional space rather than about blocks.

So the run is stopped when its basis reaches half the problem’s dimension, and the problem was made large enough that every honest width has room to converge inside that. That is a limitation of the measurement, stated where the assertion is, rather than a property of the method.

What a wider block buys, priced #

On a simple eigenvalue, where no width is required at all, the wider blocks still do something: the step count falls from 19 to 13 as the block grows from one to six. And the product count rises from 19 to 78.

Six iterations removed for fifty-nine extra products with A: about ten products with A per iteration saved.

That is not obviously a bad trade, and this site has the field that says why. An iteration of a Krylov method is a synchronisation — every processor holding part of the vector has to agree on an inner product before the next step can start — and the cost field’s own finding is that three factorisations of one matrix rank differently in messages and in words: 48, 4 and 4 communication rounds against 1,170, 1,170 and 2,160 words moved, with the method that sends the fewest messages sending the most words.

A block trade is that trade inside an eigensolver. Ten products with A is cheap against a global reduction when the reduction is what the machine is slow at, and expensive when it is not. What the measurement supplies is the exchange rate, which is what turns a preference into a decision.

The mechanism that is supposed to make this unimportant #

There is a standard answer to how wide, and it is that the width does not much matter because the block deflates. When a new block direction turns out to be numerically dependent on what has already been built, it is dropped, the width falls, and the method finds its own size.

Measured, from a random starting block, that never happens.

The first row is the finding: a random block never narrows, at any width from two to six, at any multiplicity, until the whole space is exhausted. The block Krylov space of independent random vectors does not lose rank, so there is nothing for the mechanism to detect.

The other two rows are the positive controls, and they are the reason the first row is a measurement rather than a broken detector. A block handed a repeated column drops it before the first product with A and keeps the width it is left with. A block whose columns all lie in the span of two eigenvectors starts at two — the other columns were never independent — and terminates after one step having found the whole subspace, which is the one case where a block should stop.

A block narrows only when it was given something it already had.

What a too-narrow block returns #

The failure is worth looking at directly, because it does not look like a failure.

A block of two, on a triple eigenvalue, after twenty steps of a 200-dimensional problem, returns two values at the repeated eigenvalue: 9.999999999989216 and 9.999999999945066, in error by 1.1·10⁻¹¹ and 5.5·10⁻¹¹. Both are excellent. The vectors that go with them are an orthonormal pair spanning a genuine two-dimensional invariant subspace of A. Every residual is small, every bound is tight, and nothing anywhere in the computation is wrong.

The third copy is simply absent, and the same run with one more column returns it.

This is the shape the subspace field already named from the other direction: a plane can be well determined while the vectors in it are not, and a method that has found part of an eigenspace has found a smaller invariant subspace correctly. There is no internal quantity that separates the eigenvalue is double and both copies are here from the eigenvalue is triple and two copies are here, because the arithmetic of the first situation is exactly what the method is doing in the second.

The only routes out are external. Count the copies and compare against a multiplicity known in advance; or widen the block and see whether another copy appears, which costs a whole extra run; or compute a trace or a determinant by some independent route and check it against the spectrum found. Each of those is information from outside the iteration, which is the honest summary: a block method cannot discover the multiplicity, it can only be told it.

Where the extra columns go #

A wider block than the multiplicity is not doing nothing. It is running a wider Krylov space, and a wider space converges to the other eigenvalues faster too — which is why the step count falls at all.

That is worth separating from the multiplicity question because it is the reason the trade is not absurd. A block of six on a simple eigenvalue is not six copies of a search for one direction; it is a search over a six-dimensional starting space, and the extremes of the spectrum are reached from it sooner. The step count falling from 19 to 13 is that effect and nothing else.

What the measurement says is only that the effect is weak — six columns for a 32% reduction in iterations — and that it is paid for at four times the arithmetic. A method whose iteration cost was dominated by something other than the products with A, which is exactly what a distributed eigensolver’s is, would read that table the other way up.

A note on what was measured and what was not #

Three things this essay does not settle, and each of them would change the numbers.

The spectrum is built rather than found. The eigenvalues are 1 to 10 in equal steps with the top one repeated, which is a spectrum with no clustering anywhere except where it was put. On a spectrum with a dense interior the step counts would all be larger and the widths would interact with the clustering in ways this construction cannot show.

The block is orthonormalised twice against everything, at every step. That is the decision restart.js records and takes: the subject is what a block can reach, not what a lost basis does. A production block method reorthogonalises selectively or not at all, and its behaviour at large widths is then a question about orthogonality rather than about spaces.

And products with A are counted, not time. The whole argument for a wide block is that its products come in a batch — b matrix-vector products that can be one matrix-matrix product, with the memory traffic amortised — which is a claim about a machine and belongs to the cost field rather than here. The exchange rate of ten products an iteration is the numerator of that argument, not its conclusion.

So the width is a decision, not a discovery #

Putting the three measurements together gives a short procedure and an honest gap in it.

If the multiplicity is known, use it. The narrowest working width is the cheapest at every multiplicity drawn, by a margin that grows with the width — 32 products against 84 at multiplicity two.

If it is not known, nothing in the method reports it. A block too narrow returns a plausible, accurate, complete-looking answer with a copy missing, and the residual bounds on the copies it did find are excellent. This is the same failure the double eigenvalue essay describes and the reason it is worth restating: the method does not fail, it succeeds at a smaller problem than the one it was given.

And running longer does not help, which is the refusal this essay publishes. It is the tempting repair and it is refuted: a block of two on a triple eigenvalue returns two copies at every step count the measurement reaches.

What is left when nothing is repeated #

Exact multiplicity is a construction. Real matrices have clusters — eigenvalues separated by 10⁻⁸ rather than by nothing — and for those the previous essay measured the other half of this story: a single-vector run separates a pair by convergence and needs 17, 18, 20 and 22 steps as the gap closes through four decades, while a block of two needs eleven at every gap.

So the block’s advantage on a cluster is a step count that does not depend on the gap, and its advantage on an exact multiplicity is that it returns an answer at all. Those are different claims and the second is the stronger one: no amount of arithmetic buys what the first buys, and the second is bought by four extra products with A.

The rule as a sentence #

The three measurements come to one sentence with a price on each clause.

A block must be at least the multiplicity, and no amount of anything else substitutes. Not more steps, not a different starting block, not a smaller tolerance. The missing copy is not in the space.

Above the multiplicity it buys iterations at about ten products with A each. Whether that is worth paying is a question about the machine and not about the matrix, and the answer changes with the ratio of a synchronisation’s cost to a product’s.

And the width will not choose itself. The deflation mechanism that is supposed to let a method find its own size fires only on a block that was handed a direction it already had, which a random start never is.

What the drag does #

The slider is the multiplicity, and each position removes one more width from the left of the figure and moves the cheapest bar one place right. Nothing else about the picture changes, which is the point: the rule is min(b, d) and the figure is that expression drawn four times.

The one thing worth watching for is the fourth position. At multiplicity four the cheapest working width costs 64 products where multiplicity one costs 19 — so an eigenvalue’s multiplicity is a cost multiplier on the method that can find it, and there is no width, no step count and no starting vector that avoids it.