Residual — where it appears
Named by 71 essays across 20 fields — each of them below, with the objects they name alongside it.
Orthogonal is a number
"Q is orthogonal" is a claim about a measurable quantity, ‖QᵀQ − I‖, and on the eight-by-eight Hilbert matrix two standard algorithms return 10⁻¹⁵ and 1 for it. The one that returns 1 still reconstructs the matrix perfectly, which is why nothing warns you.
The exact answer to a nearby problem
A good algorithm does not give an approximate answer to your problem. It gives the exact answer to a problem very close to yours — and once that is the definition, a wrong result has two possible authors and they can be measured apart.
The matrix that is one row
A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly. An eigensolver spends a sweep of Jacobi rotations over 256 entries arriving at the same answer, and agrees to 1.2·10⁻¹⁵.
The projection and the right angle
The least-squares solution is the one whose residual is perpendicular to everything the columns can reach. That is not a mnemonic — it is an equation, Aᵀr = 0, and the computed answer satisfies it to 10⁻¹⁶.
The same arithmetic at a different price
A blocked and an unblocked elimination perform 72,568 operations each — the same operations, associated differently — choose the same pivots, and return a factorisation identical to the last bit: ‖PA − LU‖/‖A‖ = 4.487946226420872·10⁻¹⁶ in both. One of them moves 41,332 words between fast and slow memory and the other moves 19,476.
Elimination is a sequence of choices
Gaussian elimination is taught as a procedure with no decisions in it. There is one decision at every step — which row to use — and every stability property the algorithm has comes from making it well.
The rate the condition number predicts
Conjugate gradients converge at a rate governed by the square root of the condition number. That is a bound rather than an estimate, it is provable, and it is loose enough that provisioning iterations from it wastes nine out of ten.
A small residual is not a small error
Substituting the answer back and finding that it fits is the most natural check there is, and it verifies the wrong thing. A residual of 10⁻¹⁷ is entirely compatible with an answer whose second digit is wrong.
An orthogonalisation nobody calls one
Conjugate gradients are derived as a minimisation and behave as an orthogonalisation, which is why the finite-termination property in every textbook is not a property the method has in floating point.
The part of a solver that may be rounded
A preconditioner computed and applied with a three-bit significand still returns thirteen correct digits — it costs seventeen extra iterations and nothing else. Round the working arithmetic instead and the step count barely moves while the answer loses exactly the digits the format dropped.
The valley with no bottom
A degree-nine fit's coefficients can be moved by a third of their own size before the residual changes in the sixth significant figure. The arithmetic did not lose those digits. The data never contained them.
Two ends of the same arrow
One matrix, one row moved from the front of the elimination order to the back, and the factor goes from completely dense to no fill at all. Both factorisations are exact to rounding, and nothing numerical chose between them.
The bound that is never attained
Partial pivoting's stability guarantee permits the entries to double at every step — a factor of 5.5·10¹¹ at n = 40. The measured growth on random matrices of that size is about three. The gap is eleven orders of magnitude, and the guarantee is still worth having.
Randomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.
An answer that is known
Almost every demonstration of numerical error estimates the error by computing the same thing more carefully. The Hilbert matrix does not need that: its inverse is a closed form in integers, so the true answer is available exactly and the error is measured rather than approximated.
Structure and stability stop being separable
The sparsest variable to eliminate on this matrix has a diagonal entry of 10⁻¹². Eliminating it produces the smaller factor, reproduces the matrix to 3.8·10⁻¹⁷ — better than pivoting does — and returns an answer wrong in the fifth digit.
The vector that hides it
Every quick demonstration of a parallel sum uses positive numbers, and positive numbers are the one family where the effect is absent. Measured on six inner products this site already computes, the summation condition number runs from exactly 1 to 10¹⁷ — and the safe end is where nobody makes a decision.
Buying the accuracy back
Factorise in single precision, then correct the answer using residuals computed in double, and the result is what a full double-precision solve would have given. Compute those residuals in single instead and the identical algorithm, at identical cost, recovers nothing.
The spectrum that predicts nothing
For a symmetric matrix the eigenvalues govern how fast an iteration converges. Drop symmetry and they stop governing anything — there is a matrix whose eigenvalues are as evenly spread as eigenvalues can be, on which GMRES makes no progress at all until the last possible step.
When the matrix is wrong too
Every least-squares problem here has assumed A is exact and b is not, and moved b onto the column space of A. Where both were measured, the smallest correction that makes the system consistent moves the matrix as well — and on the problems where that answer is more accurate, it has the larger residual, by construction rather than by luck.
The form that makes it affordable
One Householder reduction, done once, turns every subsequent iteration of the eigenvalue algorithm from cubic to quadratic cost. It changes no answer at all, which is why it is easy to describe as an optimisation and wrong to.
A threshold between fill and growth
One number decides how small a pivot an elimination will accept. At 0.001 the factor holds 172 entries and the matrix grows by 1,330; at 1 it holds 260 and grows by 1.2. The libraries ship 0.1, and the measurement says why.
A rate that is known in advance
On the model problem, Jacobi contracts by cos(π/(n+1)) per step, Gauss–Seidel by its square, and optimally relaxed SOR by a number given in closed form. Three rates, all known before anything runs, and all measurable against what runs.
The error smoothing cannot reach
One weighted Jacobi sweep multiplies every mode of the error by a number, and the number is a sine. Half the modes are cut by three or better, and the other half come back at 0.999 — which is not a failure of the method but the fact the whole of multigrid is built on.
The same problem on a coarser grid
Restriction, the coarse operator and interpolation are three matrices with nine distinct entries between them. Two of the three are each other's transpose, and their product with the fine operator is the coarse discretisation exactly — not approximately, entry for entry, at every level.
The problem the solver was actually given
A linearisation is exact — it has the polynomial's eigenvalues, with their multiplicities, and the whole loss is arithmetic. A nonlinear eigenvalue problem does not offer that. Every algorithm replaces the function first, and the term that replacement contributes is committed before any number is rounded and appears in no residual.
Influence is decided before the data
The diagonal of the hat matrix sums to the number of columns and the response appears nowhere in it, so a fit has exactly p units of influence to hand out among m observations. The same row at h = 0.5 is a ten-fold outlier on one design and a boundary case on another, and which of those it is was settled before a single measurement was taken.
The gap refinement can close
Multiplying by a computed inverse is not backward stable, and refinement at the working precision repairs it. That much is settled. The claim beside it — that the forward error does not move — was read at one conditioning and four corrections too late. Swept over ten, it moves at every one, and it lands on the LU route's own number after a single correction.
The rounding that was not the problem
A rank-k block plus a rank-k block is a rank-2k block, exactly, so every arithmetic in this format truncates after every addition. A Cholesky performed inside it does ninety-eight of those and its residual is 1.14·10⁻⁹ against a representation error of 1.40·10⁻⁹ — the roundings cost nothing measurable.
The two numbers a caller has
Choosing between the two least-squares methods is a statement about where the noise is, and the two quantities a caller can compute are both blind to it. The residual separates the answers by 0.14 per cent where their accuracies differ by 14, and κ(A) falls from 3.54 to 2.46 across a sweep in which the error rises by a factor of sixty-two.
A knob calibrated in residuals
A formatted Cholesky has two numbers in it and only one of them is an accuracy. Across twelve trees — three sizes by four leaf sizes — the leaf moves the truncation count from 0 to 258 and moves the ranks of the blocks not at all, while the residual follows the tolerance at slopes between 1.022 and 1.046 and sits at about a tenth of it throughout.
A basis built from the points
A polynomial fit computed in monomials and in an orthogonal basis gives the same curve on exact data, and the valley essay drew the two lying on top of each other. Add 0.1% noise and they separate — by 1.7·10⁻⁵ at degree 40 and 0.004 at degree 48 — because the fitted curve moves with the basis by its condition number times the rounding times the residual. Chebyshev polynomials keep that small only on points spread like their weight; on a sample with a hole in it they reach κ = 1.55·10⁷. A basis orthogonalised against the sample points themselves stays at 1 on every set.
The eigenvalues that are answers to nothing
A rational approximant of degree five turns a six-by-six problem into a thirty-six-by-thirty-six one, and thirty-six numbers come back. Six are the answer. The rest are exact eigenvalues of the approximant, lying where the function it approximates is not a real number at all.
Five indices are cheaper than two
The same 4,096 unknowns cost 1.049·10⁶ multiplications indexed as a 64 × 64 grid and 1.966·10⁵ indexed as six axes of four. The dense factorisation that ignores the indexing costs 4.581·10¹⁰ at every one of them, and the residual improves in the same direction as the cost.
The count that is not the budget
A Cholesky performed inside a low-rank format truncates 0, 2, 10, 34 and 98 times as the leaf falls from 128 to 8, and those five integers are the same at every accuracy from 10⁻¹² to 10⁻². Across all ten decades the factorisation's residual stays below the representation's own error at a ratio between 0.81 and 1.00 — with two entries that read 1.83 and 1.78, and neither of them is accumulation.
A stopping test is a race
One matrix, one right-hand side, one tolerance, thirteen partition counts — and eleven different iteration counts between 674 and 690. Every run converged, every answer is right to the accuracy asked for, and what differs is the bill.
An accuracy that is a backward error
Every backward error measured so far is something an algorithm produced and somebody then measured. This one is a line in the program. Solving with a compressed matrix gives a residual that is the compression's own error, at a slope of 1.000 over ten decades, so the knob that sets the storage sets the backward error directly.
A stopping rule that follows the run it is given
A preconditioner that reaches the answer four times sooner leaves four steps within 10% of its best instead of sixteen, and a rule that stops by the residual ought to miss so narrow a window more often. Over forty draws of the noise it misses it less: the discrepancy principle stops at 1.030 times the preconditioned run's best against 1.073 times the plain run's. And past the edge it stops within a factor of 1.7 of a run whose own best is 5.5 times Tikhonov's — faithful to a run that has already failed.
One minus a leverage is a subtraction
Every deletion diagnostic divides by 1 − h, and computing it as one minus a computed leverage loses digits in proportion to 1/(1 − h), however accurate the leverage. The complementary block of a QR factor gives the same number as a sum of squares and loses κ(A)·u instead: every digit on a well-conditioned design, and half the digits the subtraction loses on a design whose far point is what made 1 − h small.
Bracketing an error nobody can measure
The error of a low-rank Gramian factor is the one quantity a caller cannot compute, because computing it needs the Gramian the factor exists to avoid forming. Two numbers that can be computed sit either side of it — a rational factor known before the run, and a residual known after — and they stay a factor of four apart across a fourfold change of size.
Two observations that hide each other
Two observations at the same place, wrong by the same amount, each look harmless when deleted alone, because a fit without one still has the other. Single deletion sees the shared error cut by (1 − 2h)/(1 − h) — measured at 261 times at the far end — and only the pair's two-by-two block of the hat matrix says what the two of them hold.
Feasible and wrong
A third constraint that nearly repeats the first takes the best route's answer from 2.96·10⁻¹⁵ to 1.16·10⁻⁴, and the other two routes to no correct digit at all. Every one of those answers satisfies every constraint to 10⁻¹⁵. The quantity a caller checks after a constrained solve is the one quantity here that says nothing.
One line that buys a quarter of the run
The adaptive forcing rule has a floor on it that no published statement of the rule carries: do not solve a step to an accuracy the outer loop will not use. Removing it costs 9 to 27 per cent of the whole inner run. Keeping it costs between 23 and 2,600 times the forward error — accuracy the residual test never asked for and both runs satisfy the test either way. The line is a trade between a residual and an error, and which of the two the caller meant decides whether it is a saving.
Three errors and one number
This site's identity has two factors and a division of blame between them. Two fields have now added a third party and a fourth, and only one of the four is a property of anything — the others are decisions, made before the arithmetic, reported by nothing.
The fifth author
Four authors of a wrong answer have been named already and each is a statement about one computation. The fifth is not: it is what separates two computations that are both correct, it is a backward error of measurable size, and no residual, bound or condition number contains it.
The factor a sparse code keeps anyway
Every deletion diagnostic divides by one minus a leverage, and computing it as a subtraction loses a digit for every decade the leverage is from one. The route that does not subtract needs the orthogonal factor, which a sparse factorisation is supposed not to have. Three repairs that avoid it all fail at exactly a unit of roundoff over the divisor — and the fourth, which reaches the orthogonal factor through the Householder vectors a sparse code keeps in order to solve anything at all, returns the same bits as a stored factor in 900 operations.
A corner the penalty can afford
Every smooth reading of the deconvolution's grid needed about forty points and then stopped improving, and the step was the suspect. Give the step one coefficient of its own and forty-eight points reach an error of 0.0070 at 0.1% noise, against 0.118 for the best smooth reading on ninety-six — the step was most of the error. But the same step given two coefficients recovers half as well, and given a doubled node at each edge it recovers worse than no breakpoint at all, while representing the signal to 0.07%. What decides is what the penalty is charged for the corner, and whether the data can say where it is.
The residual the solution cannot hold
Sorting a weighted fit's rows heaviest first gave every digit of one minus the heavy row's leverage back. It gives nothing back to the heavy row's residual, if that residual is computed the way every textbook computes it — as the datum minus the fitted value. The fitted value is a double, and a double cannot resolve a misfit smaller than its own last digit times the weight: at a weight of 4²⁴ the residual formed from the solution is wrong in its second digit in every order, and forming the subtraction exactly changes nothing. Taken from the same orthogonal factor as the divisor, the residual keeps fifteen digits, and so does Cook's distance at 3.4·10¹⁷.
The residual turns before the error doubles
Regularise a saddle-point matrix past the Hessian's most negative eigenvalue and its pivot signs certify every shallow saddle as a minimum; refinement against the unregularised matrix keeps the test, as a rate, and a saddle at a hundredth of the regularisation grows by only 1.0014 a step — 485 steps to double. That was read as hundreds of steps before the history says anything. The residual, which is what a solver actually has, says it at step 62: a fit of its logarithm over the last ten steps turns positive there and stays positive, while the minimum's is negative from step 10. Across five regularisations the verdict comes at an eighth of the doubling time.
A floor with a cliff at one
Inexact Newton's adaptive forcing rule is used with a floor: never ask the inner solve for less than c times the outer tolerance, relative to the current residual, with c a half. Swept from a hundredth to ten, the constant trades with no knee at all — the forward error rises in proportion to c, the inner work falls by a few per cent a decade — and then, just past one, the run stops converging: at c = 3 it hits the outer limit on four problems of five, having asked every step for less than the stopping test needs. And the accuracy the floor gives up at c = ½ is no planning number: across five problems and four tolerances it runs from nothing to a factor of 48,000.
Nine steps of pessimism
A proved bound is 8 to 26 times the error it bounds, at every precision from 16 to 40 significand bits. A carried interval is (√2)ᵐ times too wide after m re-enclosures. The two cross between eight and nine, so the method everybody warns against is the tighter of the two for a short computation.
The residual the appended block cannot remove
Appending b as one more block made block modified Gram–Schmidt solve least squares as well as Householder, ten million times better than the same Q through Qᵀb at κ = 10⁸ — on problems with no residual. Give b a component outside the range and every stable route's error rises with it, while Qᵀb's, already at κ²u, does not move. The appended block's advantage then falls as one over the residual: 5,400 at a relative residual of 10⁻⁴, 54 at a per cent, none at one. It never falls behind Householder by more than a factor of four. What the residual decides is whether the extra block is worth its synchronisations, and the answer is yes up to a residual of about a per cent.
The right-hand side that hides the saddle
Refinement against an unregularised saddle-point matrix gives the second-order verdict the pivot signs cannot, from step 62 on the shallowest saddle — for one right-hand side. The verdict depends on how much of the growing direction the right-hand side contains, and it can contain none. Each decade removed delays the verdict by a fixed number of steps, 147 on the shallowest saddle, set by the growth against the minimum's slowest contraction rather than by the growth alone, which predicted 1,611. Rounding stops the hiding at about 2,700 steps — but by then refinement has solved the system to a residual of 2.6 times ten to the minus thirteen, and any stopping test has already accepted it. A random kick to the starting point costs nothing and finds it.
The reading that never moves
Across thirty runs — five grids from 36 to 196 unknowns, six working precisions from 53 significand bits down to 8 — the residual conjugate gradients stops on stays between 1.10·10⁻¹³ and 9.95·10⁻¹³. Over the same thirty runs the error of the answer spans a factor of 2.39·10¹¹, and the step count more than doubles. The one number the run publishes is the only one that responds to neither axis.
One hyperplane hides nothing
Iterative refinement against a saddle-point matrix gives its verdict when the growing direction overtakes the minimum's slowest decay, and a right-hand side with that direction removed delays it by a fixed number of steps a decade. With two negative curvatures, the prediction was that hiding both is paid for by the faster, and that hiding only the faster leaves the slower one's race to run. The first half holds to half a per cent on three pairs, and to one and a half on two whose curvatures differ by a factor of two and of 1.2. The second does not: hiding either direction alone moves the verdict by a fixed handful of steps, the same at two decades as at sixteen, because the direction left in view is already growing. Only the intersection of the two hyperplanes hides anything — and it hides less than either curvature can alone, 1,127 steps at worst against 2,907, with random right-hand sides' slowest at 79 against 417.
The worst residual belongs to the route
Every stable least-squares route's error rises with the residual at about a fiftieth of the bound κ²uρ, and the question left open was whether a residual aimed at the weak directions closes the gap. It can be aimed exactly: the map from residual to error is, on these problems, one direction and rounding. Aimed, Householder's constant rises from a median of 0.014 to 0.11 — √(m − n) = 6.9 times a typical direction, at 32, 64 and 128 rows to three figures — and stops a factor of nine short of the bound. The direction is each route's own: aimed at one, another route draws a fifth of its worst. And aimed at the appended block, the one-per-cent rule that made it worth its extra block falls to half a per cent, with the block twelve times behind Householder on the same data.
A target the residual can promise
A caller who wants inexact Newton's answer to six digits usually passes 10⁻⁶ as the residual tolerance, and on five problems at four targets that misses by 7 to 35,000 times. Divide the target by a condition number and it is met on every cell where a residual can certify it — and the condition number need not be known: the Ritz values conjugate gradients produces on the way give the Jacobian's own, settled by the sixth Newton step and within eleven per cent of the truth at the end, and two to nineteen times below the linear part's. Stopped that way, with the usual floor under the forcing term, the run lands within a fifth of its target and is cheaper on 16 of 19 cells than the unfloored run stopped by someone who knows the answer.
The honest residual is not a stopping test
A conjugate-gradient run in reduced working precision reports a residual pinned near 10⁻¹² while its error spans eleven orders, and the repair was to recompute the residual in double. As a report it works: on thirty runs it lands within a factor of a quarter to five of the error. As the thing to stop on it fails outright: below 53 bits it is passed on none of twenty-five runs, which go on to the 300-step cap or until their own recurrence collapses — 7,694 products in all against 605. One clause fixes it. Stop also when two checks in a row fail to halve the double residual, and every run ends within thirty-six products, at the same error, reporting a number that means something — and at 8 and 11 bits on the larger grids, sooner than the recurrence's own test.
Five steps is a rate
A stagnation clause that checks the true residual every five steps, and stops when two checks in a row fail to halve it, stopped every reduced-precision conjugate-gradient run at the error it could reach. The worry was that five steps is a property of one fast problem, and the prediction was that on the unpreconditioned Laplacian, several times slower, it would stop some runs early. It does not: unpreconditioned conjugate gradients still halves its residual every five steps on these grids, and the clause stops all twenty runs within a tenth of the least error. Scale the same Laplacian's rows by a decade and a half and it stops nineteen of twenty at step fifteen, up to 775,000 times the attainable error. A clause that sets each interval from the reduction it last saw stops every run of all three kinds within two fifths of it — and on the fast runs pays for that with eight to twelve times as many steps past the best.
A problem with no answer
If two matrices share a null vector then det(A − λB) is identically zero and every λ is an eigenvalue, which means none of them is. Perturb such a pencil by a ten-billionth and a solver returns six numbers with residuals below 10⁻⁹. Change the seed and it returns six different numbers, spread over forty-four, with residuals just as small.
The zero that means it is finished
Every Krylov method ends by dividing by a number the previous step produced, and when that number is zero the recurrence stops. In Arnoldi the stop is the answer — the subspace has closed, the solution is inside it, and the residual is at the unit roundoff. The literature calls it a lucky breakdown, and the adjective is doing real work.
A backward error the answer does not feel
Both ways of solving AX + XB = C leave a residual at the rounding level, and for a linear system that would be backward stability. For the equation it is not: the smallest perturbation of A, B and C that makes the computed X exact can be far larger. On a family built to make it so — X increasingly ill conditioned, C increasingly small beside AX — the structured backward error of Bartels and Stewart's solution climbs to 2.1·10⁵ times its residual, and the Kronecker system's, whose residual is four times smaller, to 2.0·10⁶, within the bound Higham's μ sets. And the error of the answer does not move. Against the exact X it stays where the size of C puts it, 6·10⁻¹⁵ to 1·10⁻⁹, across eight decades of κ(X). The perturbation that makes the backward error large has to sit on C, along directions X is insensitive to, and so the backward error rises and the answer never feels it.
A floor the error has not reached
The residual a reduced-precision conjugate-gradient run stops on, recomputed in double, has a floor, and the floor can be predicted: on sixty runs of three problems it sits within a factor of 3.3 of a constant times u·‖|A||x|‖/‖b‖. The prediction was that the unit roundoff and the grid would be enough. They are not — adding the grid's size or κ(A) makes the prediction worse than u alone — and the quantity that works reads the solution. Nor is the floor a signal to stop. When the residual first comes within four times its own floor, the error is still a median 4.6 to 12.6 times its least, and on the slowest problem the least error arrives a median 76 steps later. A clause that stops there stops some run of every problem at three times its least error or more. What the floor can do is tell a run when to start checking often: switching to five-step checks within four times it keeps the error within a tenth of its least on both Laplacian problems and cuts the rate-set clause's overrun from 1,661 steps to 198.
The same zero, and nothing was found
Change the recurrence by two lines and the divisor stops being a norm. It becomes an inner product of two vectors from two different sequences, and an inner product of two different vectors is zero on a whole hyperplane — with neither vector anywhere near zero, nothing invariant, and nothing converged. The arithmetic event is identical and the meaning is opposite.
The residual knew the error
A Sylvester solve's structured backward error climbed by a factor of 26,000 while its forward error did not move, and the reading was that the condition number belonging to those structured perturbations must fall by the same factor. It was predicted to fall by at least ten thousand across the sweep, and its product with the backward error to match the forward error within ten. Neither happens. The structured condition number rises, by a factor of 2.8 at every size of C, because it is a worst case over every direction a perturbation of that size could take, and the backward error's perturbation takes the most harmless one. Their product overstates the error by up to 3·10⁶ on one route and 9·10⁶ on the other. The relative residual times the plain inverse of the Kronecker matrix's smallest singular value is within a factor of 0.96 to 9.7 of the forward error on all 120 solves.
A later look is a worse stop
Every stopping test for reduced-precision conjugate gradients had read the residual, and the residual flattens tens of steps before the error stops falling. The method carries a cheap lower bound on its own energy error — the sum of each step's step length times its squared residual over a window of steps that follow — and a clause that stops when that bound falls below the working precision's share of the iterate stops twenty runs on the scaled Laplacian within 1.22 times their least error, a third of the residual clause's overrun. The prediction that it would stop within thirty steps of the least on the median run misses by three. And the window turns out to be a pure delay: in reduced precision the error creeps back up after its least, so the longer the window waits, the worse the stop.
A short window from the start
Conjugate gradients carries a cheap lower bound on its own energy error, summed over a window of later steps, and a clause that stops when it falls below the working precision is safe — but the window is a pure delay. A window that starts at twenty and halves each time the estimate falls by a decade was predicted to keep the long window's safety and lose most of its delay. It loses the delay: under half window 20's overrun. It does not stop every run within 1.12 of its least error, as predicted; its worst is 1.126. And a plain window of five, which never needed to shrink, beats it on both counts at once — 1.097 at worst, 239 steps past the least in all against 335. The thing the shrinking was meant to avoid, stopping before the least, costs at most a few per cent, because near its least the error is flat.
A bound on the fall, not the error
A five-step window in Hestenes and Stiefel's error clause stopped forty steady conjugate-gradient runs promptly and safely, and was predicted to stay safe through a stall, because a lower bound on the error should sit just below an error that is sitting still. On twenty runs that stall because rounding has made them repeat themselves, it does: the bound stays above half the error on every stalled step and window 5 stops within 1.12 of the least. On runs that stall in exact arithmetic — one eigenvalue far below the other forty-seven, carrying a share of the energy — it stops more than half again too high on six runs of twenty-four, and on two at nine and ten times the least. The window sum is the energy the error lost over the window, which is a lower bound only because what is left is not negative. On a stall the loss is the other eigenvalues' remainder; it falls geometrically while the error waits, by a factor of about the square root of the isolated eigenvalue, and at low precision it crosses the threshold first.
An iterate that must be made smaller
Applying a Kronecker-sum operator to a low-rank iterate multiplies its ranks by d and adding two of them adds their ranks, so a solver in a compressed format cannot keep what it produces. Every step is followed by a truncation — and whether that truncation is a floor on the residual depends on the right-hand side rather than on the truncation.
A run that is over at step five
A conjugate gradient whose every iterate is cut to a rank budget reaches the floor that budget allows at step 5, 36, 42 or 59, and then does nothing for the rest of the run. Four times the iterations move the floor by a factor of 1.8, and past the answer's own rank they move it the wrong way.
The same budget, spent five ways
A restarted method has one budget — products with A — and two ways to spend it, in many short cycles or a few long ones. At about a hundred and forty products the answer is the same to a factor of seven whichever split is chosen, and the residual bound the method reports spans ten orders of magnitude across the same five runs.
Named alongside it
The objects these essays reach for when they reach for this one.
Condition numberForward errorBackward errorConjugate gradientsStopping criterionUnit roundoffExact ground truthKrylov subspaceLeast squaresMixed-precisionHouseholder reflectionLow-rank approximation