Numerical Linear Algebra
where the algebra stops being the arithmetic
Methods that were designed apart

The second value was not late

Holding conjugate gradients' new basis vectors off the first Ritz vector to converge was predicted to keep its filter power within 10⁻⁶ of a fully reorthogonalised run until the second Ritz value converged, six to twelve steps later. It removes every copy of the largest value, as predicted, on all seventy-two draws. It holds the power for at most one step. The second value converges one or two steps after the first, the third and fourth with it, and the basis loses orthogonality toward all of them at once. Holding off every Ritz vector as it converges holds the two runs together ten steps longer at least, and to the end of the run on the narrowest blur.
19 min read 5 figures Measured, not assumedIdentical algebra, different arithmeticWhose fault is itTwo routes to a number

Worth reading first: A parameter that counts steps · An inner product with no fixed sign.

The runs part before the copy compared two computations of conjugate gradients on the normal equations of a blurring matrix that are one computation in exact arithmetic: the short recurrence, which keeps two vectors and forgets the rest, and Golub–Kahan bidiagonalisation with every new basis vector reorthogonalised against all the earlier ones. Step by step, the filter power mm — the smallest Ritz value times the sum of the reciprocals of all of them, the number that says how sharply the method’s filter cuts — agreed between the two to eleven digits, and then, within a step or two of the short recurrence’s basis losing orthogonality past 10−410^{-4}, it did not agree to one. That happened four to eight steps after the leading Ritz value converged, and three to seventeen steps before any Ritz value appeared twice.

Its last section turned that order of events into a repair and a prediction:

If the parting is caused by the first converged Ritz vector, then orthogonalising each new basis vector against that one vector, from the step it converges to 10−810^{-8}, should hold the two runs together. The prediction with a sign is that on all seventy-two draws this keeps the two values of mm within 10−610^{-6} until the second Ritz value converges, which on these blurs is six to twelve steps later than the first, and that it removes the first copy entirely while leaving the second.

The repair does exactly one of the things it was meant to. It removes the copy. It does not hold the runs together, and the reason is in the number the prediction quoted in passing: the second Ritz value is not six to twelve steps behind the first. It is one or two.

Four ways of running the same method

The problems are unchanged: a Gaussian blur 1.5, 2.5 or 4 samples wide on sixty-four points, noise of one per cent or a tenth of one per cent, twelve draws of each, sixty steps. The fully reorthogonalised run is the reference, and against it four short-recurrence runs are compared, all from one loop that differs only in what it holds off:

  • nothing — the short recurrence as it stands. This is the control, and it reproduces the earlier essay’s numbers exactly: the same parting step and the same first copy on all seventy-two draws.
  • one vector — the prediction’s repair. At the first step where the run’s own largest Ritz value is within 10−810^{-8} of the largest squared singular value, its Ritz vector is formed from the basis so far, once, and from then on every new normal-equations residual ATrA^{\mathsf T} r has its component along that vector removed before it is used — twice, in the modified order, for the reason two Gram–Schmidts gives. This is selective orthogonalisation in the form Parlett and Scott gave it, with one vector.
  • every vector, formed at 10−810^{-8} — the same, for each Ritz value in turn: whenever the jj-th largest reaches 10−810^{-8} of the jj-th squared singular value, its Ritz vector joins the held set.
  • every vector, formed at 10−1310^{-13} — the same again, but each vector is formed only once its value has reached rounding level, when the vector is as accurate as it will get.

Forming a Ritz vector needed one correction that is worth stating, because it fails silently. Conjugate gradients’ normalised residuals are the Lanczos vectors of ATAA^{\mathsf T} A only up to a sign that alternates with the step; the tridiagonal its coefficients define assumes the alternation. Built without it, the “converged” Ritz vector was 0.5 to 0.8 away from the singular vector it stood for, and every held-off run behaved like the short recurrence for a reason that had nothing to do with the question. With the signs restored, the vector formed at 10−810^{-8} is within about 10−410^{-4} of the leading right singular vector on the narrowest blur, and on all but three draws of the wider two within 10−510^{-5}, down to 2×10−62 \times 10^{-6} — about the square root of the eigenvalue’s error or better, which is the textbook relation.

One vector buys a step

On six blurring problems, twelve draws each, the step at which conjugate gradients' filter power m parts from the fully reorthogonalised run's when the short recurrence holds off no Ritz vector, the first to converge, or every one as it converges, beside the steps the first and second Ritz values convergeblur 1.5, noise 1%: first Ritz value converged at 23, second at 25; the short recurrence parts at 31, one vector held off parts at 31, every vector, formed at 10⁻¹³ parts at 49, every vector, formed at 10⁻⁸ parts at no step inside sixty; blur 2.5, noise 1%: first Ritz value converged at 15, second at 16; the short recurrence parts at 21, one vector held off parts at 21, every vector, formed at 10⁻¹³ parts at 30, every vector, formed at 10⁻⁸ parts at 40; blur 4, noise 1%: first Ritz value converged at 10, second at 11; the short recurrence parts at 14, one vector held off parts at 15, every vector, formed at 10⁻¹³ parts at 21, every vector, formed at 10⁻⁸ parts at 27; blur 1.5, noise 0.1%: first Ritz value converged at 23, second at 25; the short recurrence parts at 31, one vector held off parts at 31, every vector, formed at 10⁻¹³ parts at 47, every vector, formed at 10⁻⁸ parts at no step inside sixty; blur 2.5, noise 0.1%: first Ritz value converged at 15, second at 16; the short recurrence parts at 20, one vector held off parts at 21, every vector, formed at 10⁻¹³ parts at 30, every vector, formed at 10⁻⁸ parts at 41; blur 4, noise 0.1%: first Ritz value converged at 10, second at 11; the short recurrence parts at 14.5, one vector held off parts at 15, every vector, formed at 10⁻¹³ parts at 21, every vector, formed at 10⁻⁸ parts at 27. Each dot is a median over twelve draws and its line the range.0102030405060blur 1.5, noise 1%past 60blur 2.5, noise 1%blur 4, noise 1%blur 1.5, noise 0.1%past 60blur 2.5, noise 0.1%blur 4, noise 0.1%the short recurrenceone vector held offevery vector, formed at 10⁻¹³every vector, formed at 10⁻⁸first Ritz value convergedsecond convergedstep at which m parts from the reorthogonalised run'smedians and ranges over twelve drawsone vector buys a step at most
Fig. 1 For each problem, the step at which each way of running parts from the reorthogonalised run — its filter power more than 10⁻⁶ away — as a median over twelve draws with its range, beside the steps at which the first and second Ritz values converge. Holding off one vector parts with the short recurrence; holding off every vector parts ten to twenty steps later, or not at all.

The figure at the top of the page is the result. The red dots, the short recurrence, part at 31 on the narrowest blur, 20 or 21 on the middle one and 14 or 15 on the widest. The violet dots, holding off the first converged vector, sit on top of them: on forty draws at the same step, on thirty-two one step later, never more. One step of agreement is bought on some draws, and nothing that changes where a stopping rule reading mm would land.

The copy half of the prediction, though, is exactly right.

Over seventy-two draws of six blurring problems, which Ritz value each way of running conjugate gradients copies first: the largest, the second, the third, a lower one, or none within sixty stepsthe short recurrence: 70 the largest, 0 the second, 1 the third, 1 a lower one, 0 none in sixty; one vector held off: 0 the largest, 41 the second, 31 the third, 0 a lower one, 0 none in sixty; every vector, formed at 10⁻¹³: 0 the largest, 0 the second, 0 the third, 72 a lower one, 0 none in sixty; every vector, formed at 10⁻⁸: 0 the largest, 0 the second, 0 the third, 39 a lower one, 33 none in sixty.the short recurrence70one vector held off4131every vector, formed at 10⁻¹³72every vector, formed at 10⁻⁸3933the largestthe secondthe thirda lower onenone in sixtycounts of seventy-two drawsthe largest is never copied again
Fig. 2 Over seventy-two draws, which Ritz value each way of running copies first: the largest, the second, the third, a lower one, or none within sixty steps. Holding off one vector removes every copy of the largest and leaves copies of the second and third.

The short recurrence’s first copy is of its largest Ritz value on seventy of seventy-two draws, as an eigenvalue that arrives twice would expect: the value that converged first is the one whose direction the basis loses first, and a basis that has lost a direction finds it again. Holding that one direction off, the largest value is never copied on any draw. The first copy is instead of the second value on forty-one draws and of the third on thirty-one, and it arrives at roughly the step the short recurrence’s own first copy did — four steps earlier at most and ten later at most. The repair does what Paige’s analysis says it should, in the direction it was aimed at, and the runs part anyway.

Four values inside two steps

The prediction’s arithmetic assumed the second Ritz value would converge long after the first, leaving a window in which one held vector was the whole of the problem. The measurement says there is no such window.

One draw of the blur 2.5 samples wide at a tenth of one per cent noise: the relative error of the four largest Ritz values against the four largest squared singular values, step by stepvalue 1 within 10 to the minus 8 at step 15; value 2 within 10 to the minus 8 at step 16; value 3 within 10 to the minus 8 at step 15; value 4 within 10 to the minus 8 at step 16. The runs part at step 21.0246810121416182022242610⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1stepRitz value, relative errorvalue 1value 2value 3value 410⁻⁸at step 12:dashed: the prediction's convergence linefour values inside two steps
Fig. 3 One draw of the blur 2.5 samples wide at a tenth of one per cent noise: the relative error of the four largest Ritz values against the four largest squared singular values, step by step, with the prediction’s 10⁻⁸ line dashed. The first reaches it at step 15; the third at 15 and the second and fourth at 16. Past the parting the sorted values no longer line up.

On every draw the second value is within 10−810^{-8} no more than two steps after the first: at the same step on one draw, one step later on forty-four and two on twenty-seven. On the draw shown the first and third converge at step 15 and the second and fourth at 16. The leading values of these blurs are not separated in the way the prediction’s “six to twelve” imagined, and the spectrum says why.

The Kaniel–Paige bound puts the rate at which a Lanczos run finds its largest value in terms of one ratio: the gap from that value to the next, over the spread from the next to the smallest. A large ratio means the largest value is found early and alone. On these blurs the ratio is tiny. The largest squared singular values are 1.0015 and 0.9971 on the narrowest blur, 1.0025 and 0.9887 on the middle one, 1.0039 and 0.9656 on the widest, so the first gap is 0.4, 1.4 and 4.0 per cent of the spectrum’s width. The gaps below are no larger in kind: on the middle blur the second, third and fourth values sit 4.7, 7.7 and 10.5 per cent below the one above them. No single value stands apart. A short Krylov space cannot see one of them without seeing the others, and the run resolves the top of the spectrum as a block, at the step at which the block as a whole is separated from the long tail below it — values falling to a fifth of the largest by the tenth on the middle blur and to a few thousandths by the twentieth.

That is the opposite of the picture the prediction drew. It reasoned as if the first value converged first because it was easiest, and the second would follow when its own turn came. On a blur they converge together because none of them is easy: the run spends its first ten to twenty steps separating the top block from the tail, and the members of the block fall out within a step or two of each other once it has.

Paige’s theorem says a Lanczos basis loses orthogonality in the direction of each Ritz vector whose residual has become small, in proportion to how small — loss of orthogonality as a number with a direction, not a property a basis has or lacks. Four Ritz vectors becoming small within two steps means the loss starts in four directions at once. On the draw shown, holding off the first, the newest basis vector at step 20 has a component of 3×10−123 \times 10^{-12} along the leading right singular vector — the repair is working — and 3×10−43 \times 10^{-4}, 5×10−35 \times 10^{-3} and 5×10−55 \times 10^{-5} along the second, third and fourth. The worst inner product with an earlier basis vector goes 10−910^{-9}, 10−710^{-7}, 1.5×10−51.5 \times 10^{-5}, 2.8×10−32.8 \times 10^{-3} and 0.490.49 over steps 17 to 21, a factor of a hundred to three hundred a step, and the third singular vector carries most of it. Removing one direction of four leaves three, and the basis is gone at the step it would have gone anyway.

That is the second refutation, and it is the more useful of the two. The earlier essay blamed the parting on the first converged vector because that is the vector the textbook account follows. What the textbook follows for clarity, the spectrum does not respect: the blame belongs to every vector that converges before the parting, and on these problems that is several.

Holding them all

If every converged direction is to blame, holding off every one should hold the runs together, and it does.

One draw of the blur 2.5 samples wide at a tenth of one per cent noise: how far conjugate gradients' filter power m is from the fully reorthogonalised run's at each step, by the short recurrence, holding off the first Ritz vector to converge, and holding off every one as it convergesthe short recurrence: parts at 21; one vector held off: parts at 21; every vector, formed at 10⁻¹³: parts at 30; every vector, formed at 10⁻⁸: parts at 38. The first Ritz value converges at 15, the second at 16.blur 2.5, 0.1% noise, one drawthe short recurrence: parts at21one vector held off: parts at21every vector, formed at 10⁻¹³: parts at30every vector, formed at 10⁻⁸: parts at38010203040506010⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1stepdifference in mthe short recurrenceone vector held offevery vector, formed at 10⁻¹³every vector, formed at 10⁻⁸dashed: 10⁻⁶ · dotted: leading value convergedthe loss is not in one direction
Fig. 4 One draw at a tenth of one per cent noise: how far the filter power m of each way of running is from the reorthogonalised run’s, step by step. Drag the blur: holding off one vector follows the short recurrence on every width, and holding off every vector as it converges stays at rounding for ten or more steps longer.

On the middle blur the short recurrence and the one-vector run leave rounding together at step 19 or 20. The run holding off every vector stays below 10−1210^{-12} to step 33 and parts at 38. Over all draws: on the widest blur it parts at 25 to 29 against 14 or 15, on the middle at 37 to 44 against 20 or 21, and on the narrowest it does not part at all within the sixty steps, on all twenty-four draws. Its copies go with it: none of the largest three values is copied on any draw, the first copy where there is one is of the twenty-first value or lower, and on thirty-three draws there is no copy at all.

There is a surprise in the fourth run. Forming each vector only once its value is at rounding — when the vector is as good as it gets, within 3×10−73 \times 10^{-7} of the singular vector — is worse than forming it at 10−810^{-8}, on every one of the seventy-two draws: it parts at 19 to 23 on the widest blur, 27 to 33 on the middle and 41 to 51 on the narrowest. The reason is the order in which things happen. Between the step a value reaches 10−810^{-8} and the step it reaches rounding, two or three steps pass, and in those steps the basis already acquires a component along the converged direction. Holding the direction off from then on cleans every later vector; it does nothing to the vectors already in the recurrence. A rough vector held early protects more than an exact one held late, because orthogonality lost is not recovered by orthogonalising what comes after.

What holding costs

Holding off every Ritz vector as its value converges: the number of vectors held at each step, median over twelve draws at a tenth of one per cent noise for each blur, beside the step count a full reorthogonalisation orthogonalises againstblur 1.5: 0 vectors held at step 20, 54 at step 60; m parts at no step inside sixty; blur 2.5: 12 vectors held at step 20, 36.5 at step 60; m parts at 41; blur 4: 16 vectors held at step 20, 23 at step 60; m parts at 27.01020304050600102030405060stepvectors held offfull reorthogonalisationblur 1.5blur 2.5blur 4dot: where m partsholding helps by holding most
Fig. 5 Holding off every Ritz vector as its value converges: how many vectors are held at each step, median over twelve draws at a tenth of one per cent noise, for each blur, beside the k vectors a full reorthogonalisation uses at step k. Dots mark where m parts.

The repair that works is not cheap. On the widest blur the held set grows from the tenth step at nearly one vector a step and holds 21 to 26 vectors when the runs finally part; on the middle blur, 32 to 39. On the narrowest, which never parts, it holds 54 to 56 of a possible 60 by the last step. Each held vector costs an inner product and an update on every later step, so near the end this is most of the cost of full reorthogonalisation, plus the Ritz vectors’ own formation. On these problems almost every Ritz value converges before the run ends, and holding off every converged vector converges on holding off nearly all of them.

That is the honest form of the result. The short recurrence is cheap because it remembers nothing, and the departure from the reorthogonalised run is the price of remembering nothing: it costs nothing until the leading values converge, then everything within two steps. An orthogonalisation nobody calls one made the general point that conjugate gradients is a Gram–Schmidt process with most of its work left undone; what the measurement adds is that on a blur, the work it leaves undone is needed in many directions at once, not in one.

What it means for a stopping rule

The earlier essays read mm as the filter’s shape and used it to say where conjugate gradients stands relative to its answer. The copies cost steps, not the filter found that past the answer the copies leave the filter’s shape alone and cost steps instead, and a power the spectrum does not set found the power varies by the draw. The runs part before the copy and this essay together move one practical line: any reading of a short-recurrence run’s Ritz values that relies on their agreeing with the exact-arithmetic method is good until four to eight steps after the leading value converges, and holding off one vector does not extend it. Where the answer itself falls — the step that minimises the error — depends on the noise. At one per cent it falls before the parting on 33 of 36 draws, so a rule that stops at the answer reads mm while it is still the exact one, which is what a stopping rule that follows the run it is given needs. At a tenth of one per cent it falls at or after the parting on all 36, and a rule reading mm there is reading a different quantity whichever way the basis is maintained, short of maintaining most of it.

What seventy-two draws do not settle

The blurs here have leading singular values packed close together; a problem with one dominant singular value and a wide gap below it is exactly the case the prediction imagined, and on it one held vector might hold for many steps. The convergence test uses the true singular values, which a real run does not have; Parlett and Scott’s test uses the Ritz pair’s own residual bound, which flags a vector at a different step, and the measurement here says the step matters — earlier was better. And the held set never shrinks: a vector held at step 15 is still held at step 60 though the Ritz vector it approximates may have moved. None of this changes the two refutations, which are about one vector and about timing, but each bears on what a practical selective scheme would cost.

Still open: a wide gap, the residual test, and the earliest moment

A spectrum with one value apart. Replace the blur by an operator whose largest singular value is twice the second and whose others follow the blur’s tail. The prediction with a sign is that there, and only there, holding off one vector from 10−810^{-8} delays the parting by at least as many steps as separate the first value’s convergence from the second’s, so that the earlier essay’s repair works on the spectrum its reasoning assumed.

The residual bound as the test. Form each Ritz vector when its residual bound, the last component of its eigenvector times the newest off-diagonal, falls below ε\sqrt{\varepsilon} times the largest Ritz value. The prediction is that this flags each vector one to two steps before its value reaches 10−810^{-8}, and that holding off every vector so flagged parts at least two steps later than the oracle test used here on every draw of the two wider blurs.

How early is early enough. Earlier formation helped. The prediction is that forming each vector at 10−610^{-6} instead of 10−810^{-8} still helps on the two wider blurs, and that at 10−410^{-4} it hurts, because a vector that far from its singular vector removes a component the basis needs, and the runs then part through a filter power that is too large.

Where this goes next

0102030405060blur 1.5, noise 1%blur 2.5, noise 1%blur 4, noise 1%blur 1.5, noise 0.1%1.3 of the answer at step 141, off the axisblur 2.5, noise 0.1%1.3 of the answer at step 145, off the axisblur 4, noise 0.1%leading Ritz value convergedbasis loses orthogonalitythe two runs' m partfirst copythe answer, median1.3 of the answer, medianstep of conjugate gradients on the normal equationsmedians and ranges over twelve drawsthe runs part before the copy The runs part before the copy Conjugate gradients by its short recurrence and the same iterates computed with every basis vector reorthogonalised were predicted to have the same filter power at the same step, to within 0.01, until the short recurrence found its first copy of a converged Ritz value. Before they part they agree to eleven digits, not two. And they part three to seventeen steps before the copy, at a step the blur decides and the noise does not: one to two steps after the short recurrence's basis loses orthogonality past 10⁻⁴, four to eight after the leading Ritz value converges. The difference starts at the bottom of the spectrum, where the power is made. The copy is the last thing to happen, not the first. λ = 105 timesλ = 9.55 timesλ = 95 timesλ = 8.55 timesλ = 2.952 timesλ = 2.92 timeseigenvalues that arrived more than once — the matrix has 40 distinct onesa spectrum with the wrong multiplicitiesextra copies, no reorthogonalisation25extra copies, full reorthogonalisation0worst relative error among the copies1.9·10⁻⁸steps taken of 80 asked for, full40no arithmetic error was madeevery one of these is right to eight digits An eigenvalue that arrives twice A matrix with forty distinct eigenvalues, handed to Lanczos for eighty steps, returns twenty-five extra copies of thirteen of them — the largest arriving five times. Every copy is accurate to 1.9·10⁻⁸ relative. No arithmetic error was made, nothing overflowed, and a caller counting eigenvalues gets the wrong multiplicity from a computation in which no individual number is wrong. 10203040506010¹10²squared singular values above the cornerRitz values heldshort recurrencereorthogonaliseddashed: one Ritz value per singular valuewithout copies, still not one each The copies cost steps, not the filter Past the answer, conjugate gradients holds more Ritz values than singular values above its corner, because rounding lets it find the leading ones again and again. Those copies were a suspect for why the filter's power could not be read off the spectrum. Reorthogonalising every basis vector removes them, and the run reaches the same iterate — the same best error to a per cent — in up to four times fewer steps. The power barely moves, the operator's sum still misses it on 62 draws of 72, and without copies there are still fewer Ritz values than singular values above the corner: the clusters, not the copies, broke the prediction.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Conjugate gradientsFilter factorsLanczosOrthogonality lossReorthogonalisationRitz valuesSemi-convergence