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 cheapest block is exactly the multiplicity, at every multiplicity the figure draws. At 1, 2, 3 and 4 the optimum is 1, 2, 3 and 4 wide, at 19, 32, 51 and 64 products. Never wider — the step count does keep falling, but never fast enough to pay for the extra vectors — and never narrower, because narrower does not return the answer.

That is the shape the whole page is about, and the two directions of being wrong are not comparable. Too wide costs a factor: at multiplicity two, six vectors cost 84 products against the optimum’s 32, which is 2.6 times the work for the same answer. Too narrow returns a different answer — one copy of a doubled eigenvalue instead of two, with nothing in the output to say so, which is the previous essay’s whole subject.

So the rule a caller can act on is not “find the optimum” but “do not go under”, and the cost of obeying it without knowing the multiplicity is bounded: the widest block here is 2.6 times the cheapest, and the narrowest wrong one is wrong.

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.

What a cluster does to the rule #

The rule is exact and it is about eigenvalues that are exactly equal. A matrix that arrived from a measurement does not have those. It has a cluster, and the question a code faces is how tight a cluster a narrow block can still resolve.

Steps and products for both members of a pair near 10, to a relative 10⁻⁶, against their separation:

The threshold is between 10⁻⁹ and 3·10⁻⁹ — an order of magnitude below √u, and seven above the unit roundoff. Below it a block of one never returns both, at any step count inside the cap. Above it, it does.

So the rule is the limit of a continuum rather than a cliff at exact multiplicity, and what a wider block buys on a real matrix is not access to a copy that was missing — it is insensitivity to how tight the cluster is.

Which is the more useful thing to be buying #

One number in that table needs its own sentence, because it is the one a reader will want to attach meaning to. The threshold between 10⁻⁹ and 3·10⁻⁹ is not the unit roundoff and it is not √u either, though it sits within an order of magnitude of the second. It is not a constant of the arithmetic at all: it depends on the accuracy being asked of the eigenvalues, which is 10⁻⁶ here, and on the rest of the spectrum, which sets how quickly the Krylov space resolves anything in that neighbourhood. Moving the tolerance would move it, and this measurement does not sweep that.

What the threshold is not sensitive to is worth stating too. It is not the block width — a block of one either resolves the pair or does not — and the transition is sharp: 39 steps at 3·10⁻⁹ and never at 10⁻⁹, with nothing in between at any step count inside the cap. So it behaves like a resolution limit rather than like a cost that grows without bound, which is why the column ends in a word rather than in a number.

Read the two columns as functions of the separation and they behave completely differently.

A block of one gets steadily more expensive as the cluster tightens: 20, 22, 28, 35, 38, 39 steps as the separation falls from 10⁻² to 3·10⁻⁹, and then infinity. A block of two is flat at 14 steps and 28 products at every separation measured, including exact multiplicity. Ten orders of magnitude in the input and no change in the output at all.

Priced in products the crossover sits at a separation of about 10⁻⁵. Above it a block of one is cheaper — 20 and 22 products against 28 — and below it a block of two is, and at 10⁻⁵ they tie.

That reframes the decision the essay is about. The width is not chosen against the multiplicity, which is exact and unknown; it is chosen against the separation, which is inexact and equally unknown — and a block of two removes the dependence on it entirely. Buying insensitivity to an unknown quantity is a better description of what the extra column is for than buying access to a missing eigenvector, and it is available on every matrix rather than only on the ones with an exact degeneracy in them.

It also explains why the exact-multiplicity table is the right one to lead with despite describing a case that never occurs. Exact multiplicity is where the block-of-one column becomes infinite rather than merely large, so it is the setting in which the rule can be stated as a theorem about dimensions. Everything softer is this section, and the softening is a cost curve rather than a different rule.

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.

The block that block-diagonalises #

A block wide enough to hold a multiplicity is one question; how well determined the resulting subspace is, is another, and the second is answered by a quantity from a matrix equation rather than from the spectrum.