The same budget, spent five ways

A restarted eigenvalue method has one currency. Orthogonalising a basis is arithmetic on vectors the machine already holds, solving the small projected problem is a dense computation on a matrix of order k + p, and neither of them touches the operator. The product with A is the only thing that does, and on the problems the method exists for it is the only thing that costs anything.

That currency can be spent two ways. Keep k Ritz values, work in a basis of k + p, and each cycle costs k + 2p products: k + p steps of the recurrence, and p more to apply the filter that starts the next cycle. A small p buys many short cycles. A large p buys few long ones. The two are presented in every description of the method as a memory budget — pick p as large as the machine allows — and the essay that reads a restart as a filter ends by saying what that description leaves out and naming the measurement nobody makes: the same total number of products with A, spent as many short cycles or few long ones, is an experiment the field could run and does not.

It is run below, five ways, on one matrix with a known spectrum. The five splits agree about the answer to within a factor of seven. The number each of them reports about the answer differs by ten orders of magnitude, and it is monotone in the split, so a caller choosing between two settings by the only evidence a real run produces will choose the one that reports better and will be buying three times the memory for an improvement the reference answer does not contain.

One budget, one wanted set, five ways to divide it #

The matrix is the site’s spread spectrum at n = 40: four isolated eigenvalues at 10, 9.5, 9 and 8.5, and thirty-six more packed at intervals of 0.05 from 1.2 up to 2.95. The wanted set is k = 4, which is exactly the isolated group, and the gap below it is 5.55 against a total spread of 8.8 — a separation of 0.63 in relative terms, which is a comfortable problem rather than a hard one. That choice is deliberate: a trade between two parameters is only worth measuring where both settings work, and the last section returns to what happens when neither does.

The budget is held near a hundred and forty products with A. Five splits reach it: p = 1 with twenty-four cycles, p = 2 with sixteen, p = 4 with twelve, p = 8 with eight, and p = 12 with six. They cost 143, 126, 140, 152 and 156 products, and the small variation is arithmetic rather than slack — the count is cycles times k + 2p, less the final cycle’s p shifts, which are applied after the answer has been read and so are not charged to it. What the five differ in is the basis they hold while spending it: 5, 6, 8, 12 and 16 vectors, a factor of more than three from end to end.

Every one of the five is drawn below at its own settings, and the pictures are the same picture: two curves against the number of products with A, the residual bound the method reports for the worst of its four wanted values and the true error of that value, the second available only because the matrix was built from its spectrum. The bound is what a real code reads, and the error is what the caller wanted and cannot see.

The cheapest split arrives long before it says it has #

Read the p = 1 run cycle by cycle and it does two things in sequence rather than one. The true error falls from 6.32 at the first cycle to 1.22·10⁻⁶ at the eighth, 1.22·10⁻¹⁰ at the tenth and 1.42·10⁻¹⁴ at the twelfth, which is 71 products with A. From there it does not improve and does not degrade: every remaining cycle leaves it between 5.33·10⁻¹⁵ and 1.24·10⁻¹⁴, which is the level at which the arithmetic stops being able to tell one answer from another.

The reported bound at that same twelfth cycle is 2.83·10⁻⁷. It goes on falling for four more cycles, reaching 4.41·10⁻¹¹ at the sixteenth, and then stops at a level between 2·10⁻¹¹ and 6·10⁻¹¹ for the remaining eight. So the run holds an answer good to fourteen digits from its twelfth cycle and spends its last half producing a number that improves by nearly four orders about a quantity that has not moved at all. Half the budget of the cheapest split buys nothing but a better opinion of what the first half already found.

This is the same shape the filter essay measured along the other axis, where a fixed p = 4 was run past its own convergence and the bound turned around and rose. Here the bound does not diverge, it merely lags — and what the two have in common is that the reported quantity and the answer come apart as soon as the answer stops moving, with nothing in the run to say which of the two a reader is looking at.

Doubling the filter is the smallest change available, and it is enough to move the reported number by an order of magnitude.

An order of magnitude in the report, and half a rounding in the answer #

Between the first two splits the reported bound improves by a factor of fifteen and the budget falls by seventeen products. Read as a convergence curve, that is a clear win for the longer basis, and it is the reading every comparison of two settings is made on, because the curve is what a run draws and the error is what it cannot.

The answer moves from 1.24·10⁻¹⁴ to 7.11·10⁻¹⁵. Both numbers are multiples of the same unit. The matrix has norm 10 and the unit roundoff of binary64 is 1.11·10⁻¹⁶, so an eigenvalue of this matrix cannot be pinned closer than about 2.2·10⁻¹⁵ by any computation at all; the two errors are 5.6 and 3.2 of those units. The improvement is real in the sense that one number is smaller than the other, and it is not an improvement in accuracy, because both answers are at the floor and the difference between them is which side of a rounding the last operation fell on. The site has a name for the gap between a quantity a method reports and the quantity a caller believes it reports, and the residual a conjugate gradient recurrence prints is the same failure with the roles of the two numbers exchanged: there the reported number was far too small, here it is far too large, and in both cases nothing in the run distinguishes them.

The next split is the one the field would call the default, and it is the setting the earlier essay drew.

Identical answers, three more orders of report #

The p = 2 and p = 4 runs return the same number. Not nearly the same: the worst wanted eigenvalue is wrong by 7.105·10⁻¹⁵ in both, to every digit either computation can produce. They differ in fourteen products with A, in two vectors of memory, and in a reported bound of 4.03·10⁻¹² against 1.08·10⁻¹³ — a factor of thirty-seven separating two runs whose answers are bit-comparable.

That is the finding in its cleanest form, and it is worth stating before the two larger splits make it dramatic. The reported bound is not a noisy estimate of the error. A noisy estimate would scatter around the quantity it estimates, and a caller could average it or take its order of magnitude and be roughly right. This one moves systematically with a parameter the error does not respond to at all, which makes it a measurement of the run rather than of the answer — a quantity computed inside the projected problem, faithfully reporting how converged that small matrix’s eigenvectors are, and saying nothing about how far the operator’s own eigenvalues have been missed by. Thick restarting drives the same wedge in by a different route, letting the model itself stop describing the operator; here the model is exact and the wedge is opened by the length of the basis alone.

The next split is where the reported number leaves the range any residual on this matrix can occupy.

A reported number the arithmetic cannot supply #

βₘ|sₘ,ₖ| is the last off-diagonal of the tridiagonal times the last entry of that tridiagonal’s own eigenvector, and it is exactly the norm of the residual A y − θ y for the Ritz pair, in exact arithmetic, which is why it is quoted as one and why it is free — a number carried rather than re-derived, in this collection’s terms. The claim it makes is checkable, because the Ritz vector is available and the product with A costs one more.

At p = 1, 2 and 4 the check passes and passes precisely. The reported bounds are 6.113·10⁻¹¹, 4.028·10⁻¹² and 1.079·10⁻¹³, and the residuals of the Ritz vectors those runs actually hold are 6.113·10⁻¹¹, 4.028·10⁻¹² and 1.073·10⁻¹³ — agreement to three digits, three digits and three digits. The free number is the residual, exactly as advertised.

At p = 8 it is not. The run reports 2.372·10⁻¹⁷ and the residual of the vector it is holding is 1.751·10⁻¹⁴, seven hundred and thirty-eight times larger. At p = 12 it reports 1.417·10⁻²¹ against an actual residual of 4.384·10⁻¹⁵, which is six orders and a half.

What a residual on this matrix can be #

The floor is not an artefact of the method, and it can be measured on the one object that has no approximation in it at all. The exact eigenvectors of this matrix are known by construction; formed in binary64 and substituted back, their residuals ‖A x − λ x‖ are 5.594·10⁻¹⁵, 3.228·10⁻¹⁵, 2.442·10⁻¹⁵ and 3.884·10⁻¹⁵ for the four wanted eigenvalues, and over all forty they run between 1.834·10⁻¹⁵ and 5.594·10⁻¹⁵.

So the smallest residual any vector on this matrix has is about 2·10⁻¹⁵, and it belongs to the right answer. A run reporting 1.42·10⁻²¹ is reporting a residual six orders below the one the exact eigenvector achieves. There is no vector in this arithmetic whose residual is 1.42·10⁻²¹, so the number is not a pessimistic bound, an optimistic bound, or a bound at all — it is a quantity computed in a model of the problem, and the model is a tridiagonal whose last off-diagonal has itself collapsed to rounding noise.

This is the shape a small residual is not a small error argues from the other side. There the residual was honest and the error was not implied by it; here the error is at the floor and the residual is the quantity that has stopped being real. Both say the same thing about what substitution proves: something about the algorithm, converted into a statement about the answer by an argument nobody supplies.

The whole comparison, in one table #

The right-hand column is monotone in p across ten orders of magnitude. The column beside it moves between 1.78·10⁻¹⁵ and 1.24·10⁻¹⁴, a factor of seven, and its ordering is p = 12, then p = 2 tied with p = 4, then p = 1 tied with p = 8 — which is not a trend, and is what a quantity sitting on the rounding floor looks like when it is sampled five times.

A caller with a real problem sees the last column and not the one before it. Comparing p = 1 against p = 12, the evidence is that a longer basis has bought ten orders of accuracy for nine per cent more products with A, and on any machine where three times the memory is available that is an easy decision. The decision is wrong in its reasoning and roughly harmless in its outcome, which is the worst combination available: it will be made again where the memory is not free, on the same evidence.

Below convergence the split matters enormously #

The finding so far could be read as a shrug — five settings, one answer, choose whichever. It is not, and the reason is that the same five splits are sharply different before the budget of a hundred and forty is reached.

Cut the budget to about forty-five products and run them again. p = 4 with four cycles costs 44 products and reaches a worst error of 5.33·10⁻¹⁵. p = 12 with two cycles costs 44 products and reaches 7.11·10⁻¹⁵. p = 2 with six cycles costs 46 and reaches 1.60·10⁻¹⁴. And p = 1 with eight cycles costs 47 products and reaches 1.22·10⁻⁶ — eight orders behind the others, on the same money.

The last of those four is not drawn here, and the reason is one of this collection’s habits rather than an omission. The figure asserts that the wanted eigenvalues have been found before it will draw a convergence curve, and fed k = 4, p = 1 and eight cycles it refuses with the 4 wanted eigenvalues are found: worst error 1.22·10⁻⁶. A picture of a run that has not converged, drawn on the same axes as four that have, is a picture that invites the comparison the number forbids, so it is a measurement in prose and not a placement.

The left column is the honest ranking of the five, and on it the split matters by a factor of four and a half: sixteen products against seventy-one for the same accuracy. That is the effect a longer basis genuinely buys, and it is a real and useful effect — the filter is sharper, so each cycle separates the wanted part of the spectrum from the rest more decisively, which is what the degree of the filter was always supposed to mean.

So the curve is not reporting a fiction. It is reporting a real advantage in the wrong units and by the wrong multiple. The advantage is a factor of four and a half in cost, and it is read off a vertical axis as ten orders of magnitude in accuracy — and it is read at a budget four times larger than the point at which it had already been collected.

And the ranking inverts on the number that decides the bill #

A code cannot stop on the left column, because the error is not available to it. It stops on the right one: run until the reported bound falls below a tolerance. On that rule the five splits cost 95, 62, 44, 32 and 44 products, and the cheapest is p = 8 rather than p = 12.

The best split by the metric a real code can apply is therefore not the split the final bound recommends. p = 12 reaches the tolerance at 44 products, thirty-eight per cent more than p = 8, on four more vectors of memory — because a cycle costs it twenty-eight products, and its first one lands at 3.42·10⁻⁹, just short, so a whole second cycle is charged to crossing a threshold the first nearly cleared. A parameter whose granularity exceeds the thing it is being tested against overshoots, and the overshoot is paid in full.

That is an interior optimum in a parameter the standard advice says to maximise, and it belongs beside the one the step count turned out to have in the regularisation field: a knob with a cost at both ends, whose best value is neither of them and is not where the obvious reading of the curve points. The two are different quantities and the shape is the same, which is the argument for looking for it before assuming monotone is safe.

Where the trade stops existing #

Every number above is measured with k = 4 on a matrix whose four largest eigenvalues are isolated. The honest boundary of the whole comparison is what happens when they are not, and it is abrupt.

Ask for k = 5. The fifth-largest eigenvalue is 2.95 and its neighbour is 2.90, a gap of 0.05 against a spread of 8.8 — a relative separation of 0.0057, against 0.63 for the gap below the fourth. Three of the same splits now return worst errors of 4.46·10⁻¹ at p = 1, 8.90·10⁻² at p = 4 and 3.51·10⁻³ at p = 12. Increasing the budget does not repair it: p = 12 run for thirty cycles costs 858 products, six times the budget above, and reaches 5.67·10⁻⁴.

At k = 6 and k = 8 it is worse. Thirty cycles at p = 12 cost 888 and 948 products with A and return worst errors of 3.74·10⁻² and 1.04·10⁻¹, on a problem the same five splits solve to fourteen digits in a hundred and forty products when the wanted set is four. The figure refuses all of them, reporting the 6 wanted eigenvalues are found: worst error 0.534 at k = 6 with p = 2 and twelve cycles, and the 8 wanted eigenvalues are found: worst error 0.298 at k = 8 with p = 8 and eight.

The mechanism is not the split and no setting of it helps. A restart aims a polynomial at the boundary between the wanted set and the rest, and when that boundary falls inside a cluster whose members are 0.05 apart, no polynomial of degree twelve separates them — the roots are placed at unwanted Ritz values that are themselves indistinguishable from the wanted ones. This is where the trade being measured stops having two sides, and it belongs with the eigenvalue one vector cannot see, which is the other failure no amount of either parameter repairs. The difference is that a repeated eigenvalue is absent from the space and a clustered one is present and unresolved, so this one is a matter of degree and that one is not.

A split is worth choosing only where the wanted set has a gap under it. That condition is checkable before the run in the sense that it is a property of the problem, and it is not available before the run in the sense that the spectrum is what the method is being asked for. Which is precisely the difficulty choosing a parameter on a smaller problem is about, arriving here from the eigenvalue side.

What follows for anything that reports a convergence curve #

Do not rank two settings by where their curves end. The end of a curve past convergence is a property of the basis length, not of the answer, and across these five runs it is monotone in a parameter the answer does not respond to. Rank them by where the curves cross the tolerance, which is the quantity that decides the bill and is the only column above that a real run can read.

Stop on the bound and do not believe its value. The bound is the right thing to stop on, because it is free and because it falls monotonically until convergence. It is the wrong thing to quote, because after convergence it goes on moving — up, along the cycle axis, where a fixed split is run past its own convergence; down, past the representable floor, along the split axis here. A stopping rule and an accuracy claim are two different uses of one number, and only the first is supported. The same distinction decides whether a stopping test is a race matters to an answer or only to a schedule.

Report the basis length beside any bound. Two runs quoting 10⁻¹³ and 10⁻²¹ on the same problem differ in a parameter, not in accuracy, and a bound quoted without the m it was computed on cannot be compared with another one. The number is dimensionally a residual and is behaviourally a function of the model’s size — and m is the quantity the restart exists to hold down, since it is what decides how many extra copies of an eigenvalue come back.

Expect the improvement a tighter tolerance buys to be smaller than it looks. Asking these five runs for four more orders on the reported quantity is answered instantly by increasing p, and the answer does not change — the tolerance that buys no agreement measured the same disappointment on a linear solve, where six orders of improvement in what was requested left the run-to-run spread exactly where it was.

And measure the trade on the problem rather than inheriting it. The five splits here are separated by a factor of four and a half in cost and by nothing in accuracy, and both halves of that are properties of this spectrum. On a matrix whose wanted set sits above a gap of 0.05 the same five return nothing usable at any budget. A comparison of parameters is a measurement of a problem, which is why the essay that put four regularisation knobs on one problem had to fix the problem first, and why the number quoted for a method without its matrix is not a number about the method.