Conjugate gradients — where it appears
Named by 67 essays across 9 fields — each of them below, with the objects they name alongside it.
A parameter that counts steps
The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.
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.
The accuracy that is thrown away
A Newton step is the exact answer to a linearised problem, and the linearisation is wrong at second order. So there is a floor under how close the step can land, the floor is the square of where it started, and eleven decades of inner tolerance below it buy the same four digits at four times the price.
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.
A tolerance that reads its own residual
The cheapest constant forcing term costs 980 inner iterations and arrives with a hundred times the forward error of the dearest, which costs 9,358. A rule that sets each step's tolerance from the ratio of the last two residuals costs 1,009 and arrives with neither problem — and it is not a constant, so it does not appear on the curve the constants are compared on.
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.
Changing the condition number on purpose
Preconditioning is usually introduced as a trick that makes an iteration converge faster. It is not a trick. It is solving a different system with the same solution and a condition number chosen rather than inherited, and the new condition number is computable.
A preconditioner that changes sign
Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.
The circulant that cannot be indefinite
The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173. Average the two diagonals instead of choosing between them and the count is 7, 8, 9, 10, 10 across a factor of sixteen in size.
Two dimensions, and the cluster that thins
The same kernel, the same averaging, the same transform — applied along two axes instead of one. In one dimension the preconditioned step count is 7, 10, 10, 10; on square grids with the same unknown counts it is 10, 18, 20, 21, and the share of the spectrum near one falls from 56% to 17%.
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.
Where the drift lands
The standing rule for when a preconditioner has gone stale is to rebuild it once the matrix has changed by more than some fraction of itself. Two drifts of exactly the same relative size cost 19 iterations and 5 on the same matrix, and the quantity that separates them is not in the rule at all — the perturbation is divided by the eigenvalue it lands on.
What a rebuild is worth
One sequence, one drift, one preconditioner — and six different right answers, because the cheapest rebuild period depends on what a rebuild cost to build and on nothing else. The optimum walks from every member to every twelfth as the setup gets dearer, and the free rule that reads the iteration count beats it in the middle of that range and loses at both ends.
An expiry date the noise does not move
The polynomial description of conjugate gradients leaves the level of rounding at step 17 or 18 on this operator, at every noise level from 10% to 0.1%. The step worth stopping at moves from 3 to 44 across the same range. They coincide at about 1% noise, which is where the coincidence was first read, and it is a fact about the noise rather than about the method.
A preconditioner that arrives past the answer
On a system that is solved to convergence a preconditioner changes how fast the answer arrives and not what it is. On a problem regularised by stopping it changes where every step lands. Conjugate gradients preconditioned by AᵀA + αI reaches its best answer in one step at α = 10⁻³, and at α = 10⁻⁶ its best answer is its first step, with an error of 1.35 against the unpreconditioned run's 0.1426 — while the count of eigenvalues it has clustered at one rises from 22 to 32.
The accuracy worth paying for
Used as a preconditioner, a hierarchical representation gets better at every accuracy — the iteration count falls monotonically all the way to the tightest tolerance. The total work does not. Its minimum sits at a rank-one preconditioner on an easy problem and six decades further along on a hard one.
The penalty for keeping it is a ratio
A kept incomplete Cholesky costs 40 iterations against a rebuilt one's 10 on 64 unknowns, and 55 against 17 on 256. Across six grids the difference between the two rises by 27 per cent and the ratio between them falls by 19. Neither quantity is free of the problem's size, and the one a policy is paid in is the one that transfers worse.
A step that is not a unit of work
Landweber's iteration reaches conjugate gradients' best answer on the same deconvolution — 0.1414 against 0.1426 — at step 1,778 instead of step 20, and at 0.1% noise at step 56,234 instead of 44. Each step costs the same two products. And within 10% of its best it runs from step 7 to step 6,310, where conjugate gradients runs from 4 to 26: the slow method is the one that forgives a late stop.
A speedup with a ceiling of its own
At ρ = 0.5 the averaged circulant takes 5 conjugate gradient steps at n = 512 against an unpreconditioned 30 — and that 30 is where the unpreconditioned count stops. It reads 29, 28, 30, 30 at n = 64 to 512 and then 29, 28, 26, 27, 25 at every doubling out to 16,384, because κ has reached 99.9% of Szegő's limit and the count has nothing left to grow with.
The method that cannot use a smooth answer
On the collection's own signal four regularisers reach the same floor to a few per cent. Score them instead against answers of increasing smoothness and one stops improving. Across six decades of noise Tikhonov's error falls with a fitted slope of 0.70 whether the answer is twice or four times as smooth, while truncation's rises to 0.94 — and at 10⁻⁶ noise Tikhonov's best is 38 times truncation's.
Where the augmentation puts the cost
Add γAᵀA to the objective block of a saddle-point system and its Schur complement tends to I/γ, so the cheapest possible approximation becomes the right one and the golden-ratio spectrum arrives — within 7.6·10⁻⁶ at γ = 10⁶. MINRES falls from 21 steps to 6. The inner solve with the augmented block rises from 14 conjugate gradient steps to 43, their product does not fall at all, and the answer loses seven and a half digits on the way.
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.
Four orders of conditioning, and four steps
On a 10×10 grid the two-dimensional kernel's condition number runs from 62 at ρ = 0.5 to 818,561 at ρ = 0.98. The preconditioned step count over the same range runs 18, 21, 21, 22, 21, 19, 18, and the count of eigenvalues the preconditioner actually brings within half a unit of one does not move at all — it is 9, 11, 13, 17 at every correlation the figure will draw.
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.
Spread resistances make the loops easy
Scaled to a unit diagonal, the loop equations on the least-resistance tree get easier as a network's resistances spread — from 120 to 5.44 over six decades — and stop depending on the grid's size, while the node equations of the same flow get harder, from 538 to 4.6·10⁴. The spread that ruins the range-space formulation rescues the null-space one, though the loops' density means the work saved is a factor of two, not the factor of nine the iteration counts suggest.
The tolerance that buys no agreement
Ask for four more orders of accuracy and you get them — the answers improve by a factor of 1.5 million. The ratio between the best and the worst run is 1.34, 1.48, 1.71 and 1.17 across the same sweep. The band falls and it does not close.
What a cheap preconditioner has to leave alone
A blur approximated by a matrix the cosine transform diagonalises agrees with the operator everywhere but its first and last seven rows. Made invertible by a shift, as the exact preconditioner was, it never reaches the unpreconditioned run's floor — at α = 10⁻³ its best iterate is 0.749 against 0.143. Made invertible by leaving every eigenvalue below τ alone, it reaches 0.141 in five steps instead of twenty, and the smallest τ that keeps the floor sits at a third to a half of the Tikhonov oracle's λ at three noise levels.
The rule that is wrong in the right direction
The preconditioner's cutoff is not a new parameter. It is the regularisation parameter this field already knows how to choose, halved — and the rule criticised for choosing λ a factor of two or three too large is the one whose cutoff keeps the floor on every draw, where the rule that chooses λ to within 3% has a worst draw two hundred times off it.
A guess worth two per cent
The previous Newton step looks like a free guess at the next one, and it is worth nothing. Started from it unscaled, the inner solve costs 4 to 61 per cent more than starting from zero, because the guess is 15 to 209 times too large. Scaled by the ratio of the two residual norms it is the right size and halves the starting residual — which buys a constant handful of inner iterations, not a share, because conjugate gradients costs the logarithm of its tolerance.
The parameter neither knob is
A preconditioned run has a cutoff and a step count, and neither is the regularisation parameter. The parameter is the effective dimension of the iterate: every cutoff that works puts its own best at 23.7 to 24.3 of it, where the unpreconditioned run's best sits at 23.2, and what the cutoff buys is the rate — 1.27 of it a step with no preconditioner and 3.53 with one. The edge is where a single stride is longer than the distance left.
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.
A count that marks the edge and not the pace
The number of directions a truncated preconditioner divides is counted for free when it is built, and it was proposed as a stand-in for the stride it buys. On three blurs it is not one — the runs leave the answer at strides of 5.71, 3.44 and 2.41. What the count does predict is the edge: on all three blurs, at two noise levels, a run stops landing on the answer's path within five per cent of the point where the count reaches the answer's own effective dimension. And the halved cutoff rule, measured on one blur, crosses that line on the narrowest.
The shift had an edge, and the approximation moved it
A fast-transform preconditioner made invertible by a shift was recorded as never reaching the unpreconditioned floor, and predicted to sit off the answer's path at every shift. At a large shift it sits on the path and reaches the floor to a tenth of a per cent. It has an edge like the truncated one — but on the exact operator that edge is where the shift's own effective dimension reaches the answer's, 1.02 to 1.05 of it on six problems, and on the fast approximation it arrives at 0.49 to 0.77. The difference is sixteen samples at the ends of the signal, where the approximation is wrong and a shift divides the error by α.
Three walks and one bound
A left-to-right sum, a chain of three thousand rotations and a conjugate gradient residual recurrence share no arithmetic and no vocabulary. Each has a standard bound that is linear in whatever it accumulates against. All three come out at a half — 0.486, 0.554 and 0.507 — and nothing is rescaled.
One arc, and what each filter pays to be on it
Conjugate gradients and Tikhonov stop at the same effective dimension, and that could have meant two curves crossing once or one curve. It is one curve over a stretch — on six problems, Tikhonov and truncation reach the iteration's error at the iteration's dimension to within 7.2 per cent from 0.7 of the answer to its top — and the two separate on either side. But the curve is shared by a trade, not by an identical answer: at the same dimension Tikhonov carries 22 to 42 per cent more noise than the iteration and up to five per cent less bias.
The overshoot was the lead
Past its best, conjugate gradients' error rose more slowly than Tikhonov's at the same effective dimension — on the narrow blur at 0.1% noise Tikhonov was 2.35 times worse at 1.3 of the answer — and the reading was that the iteration spends its dimension where the data has content. Count admitted directions instead of summing factors, so that a factor of 1.81 counts once, and the lead is gone: 0.96 on that problem, and within 0.17 of one on all six from 1.1 to 1.3. Tikhonov now carries less noise than the iteration there. Below half the answer, where the three filters also disagree, the count changes nothing.
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.
A tail from Tikhonov and a corner from truncation
Below half the answer, conjugate gradients beat Tikhonov at a matched count of directions by up to 69 per cent, and the proposed measurement was the sharpness p of a roll-off between Tikhonov and truncation that matches the iteration there. Any p from 2 to 4 closes the gap to a tenth; truncation, the family's limit, reopens it to a third. But no p describes the iteration. Its filter has Tikhonov's slope exactly in its tail and a local sharpness of 2 to 5 on its shoulder, and a single fitted p is a compromise that drifts from 2.3 at the first step to 1.7 at the answer.
An augmentation read in the smallest eigenvalue
An augmented Lagrangian preconditioner's least work sat at γ = 1, 10⁴ and 1 on three systems, and two of the three optima sat where the smallest generalised eigenvalue was about 0.06 — which suggested a rule written in ν rather than γ. On twenty-four systems whose norms are all one, the least-work γ spans seven decades and ν at the optimum spans a factor of thirty, so there is no one ν. There is still a rule: take the smallest γ at which ν reaches 0.03, and the median system pays 7 per cent over its least work and the worst 29, where the best single γ pays 61. Its price is digits — twelve times the best forward error on the median system, 4,561 times on the worst.
The staircase a separable kernel builds
A block-circulant preconditioner took 18, 21, 22, 21, 19 and 18 steps on a 10 × 10 Toeplitz-block-Toeplitz system as the correlation rose from 0.5 to 0.98 and the unpreconditioned count rose from 43 to 178 — the parameter that makes the problem hard was the one the solver did not notice. That kernel factorises. The isotropic kernel with the same correlation along each axis does not, and on it the preconditioned count climbs 17, 22, 27, 29, 33, 36, while the preconditioner buys a factor of 1.4 where it bought ten. The reason is the spectrum's shape: a product of two one-dimensional spectra is a staircase of ten treads, and a kernel that is not a product gives a ramp of thirty-eight.
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.
The first step's filter, kept for the whole run
Conjugate gradients' first step applies a ramp — Tikhonov's slope up to a corner, then one — and the essay that found it proposed the ramp as a fixed method, predicting that it would match the iteration below half the answer better than any sharpened Tikhonov and lose the match near the answer. The first half holds by more than predicted: 0.044 from the iteration below half, where the best member of the family was 0.106. The second does not: near the answer the ramp is within 0.016, closer than any filter measured. And two numbers read off the iteration's own Ritz values — its tail's slope and its smallest Ritz value — reproduce it past the top as well, where every fixed filter falls ten to seventeen per cent below it.
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 symbol that builds the staircase
A block-circulant preconditioner left the isotropic kernel's spectrum a ramp of thirty-eight clusters where the separable kernel's was a staircase of ten, and the proposal was a circulant sampled from the isotropic kernel's own symbol, to gather the ramp into treads of its own. It gathers the separable kernel instead: six clusters at every grid from 4 to 10 and every correlation, sixty-four of a hundred eigenvalues at exactly one, and eight conjugate-gradient steps at every side from 6 to 16 while Chan's circulant climbs from 18 to 28. On the isotropic kernel it shortens the ramp from 38 clusters to 30 and the step count by about a sixth, and both still grow with the grid. The treads come from a Kronecker product, not from a small difference: on both kernels the matrix and its symbol circulant differ in dozens of directions.
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.
A corner chosen without the iteration
The ramp — conjugate gradients' first-step filter kept as a fixed method — matches the iteration's error at the same position, but every comparison placed it at the iterate's position, which needs the iteration. Placed instead by the iteration's own stopping rules, it was predicted to land within the same tenth of its best and earlier. The discrepancy principle does exactly that, earlier on 61 draws of 72 and dearer by a few hundredths on 71. The L-curve finds the ramp's corner as well as Tikhonov's and far better than the iteration's: twice the best on 26 draws against 44, worst 16 against 896. And GCV fails the ramp in a way it never fails the iteration — choosing a solution that discards three quarters of one direction, 696 times its best — until its first minimum from the regularised end is taken, after which the ramp is within a tenth of its best on 64 draws of 72 and never worse than 1.25.
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.
Two forcing terms, one floor
Inexact Newton's adaptive forcing rule comes in two versions, and every measurement of the floor under it used the second, which reads the ratio of the last two residuals. The first reads how wrong the linear model was at the last step, and it was natural to hope that a rule watching the model's own error would not solve its last step past what the stopping test needs. It does. Run without the floor on five problems at four forward targets, it over-solves its last step by a median of 34 times, against the second rule's 95; the floor saves 17.5 per cent of its inner work, against 16.0. Floored, the first rule is the cheaper by 4.6 per cent overall, and it buys that with Newton steps: two more on the median cell, a third less inner work on the strongly nonlinear problem, and 4.5 per cent more on the easy one.
Six steps were six eigenvalues
A circulant sampled from a separable kernel's symbol held conjugate gradients at eight steps on every grid, because the preconditioned spectrum was six values. Add a fraction ε of the isotropic kernel and the prediction was that the six treads would widen, the count would stay near eight while they stayed under one per cent, and then climb towards the isotropic count. A ten-thousandth of isotropy leaves six clusters at the one-per-cent rule and takes the count from 8 to 13–15; a millionth takes it to 11. The eight steps were finite termination on six distinct eigenvalues, not convergence on six clusters, and once the eigenvalues are distinct what a tread costs is set by its width against the solver's tolerance: at a tolerance of 10⁻⁴ a ten-thousandth of isotropy costs two steps. The widths grow in proportion to ε, and summed tread by tread they account for the climb to within four steps. Past a tenth the mixture is harder than either kernel alone — 37 steps on a 16 × 16 grid against 35 for the isotropic kernel — while its condition number is lower than both.
A power the spectrum does not set
Conjugate gradients' filter past the answer is a ramp raised to a power m between 1.27 and 1.50, read off its own Ritz values, and the power was predicted to be the blur's: computable from the decay of the singular values to within 0.1, so the iteration's filter could be built without running it. It is not. Summed over the singular values above the iteration's own corner, the decay gives anything from 0.76 to 4.3, because the Ritz values are not those singular values — fewer of them early in the run, each standing for a cluster, and more of them late, the leading ones found again and again. The power is the spacing between the smallest Ritz value and its two neighbours. And nothing depends on it: placed by GCV's first minimum, the power ramp at every m from 1 to 3 lands within a tenth of its best on 63 to 66 draws of 72.
A tolerance is not an accuracy
A fixed perturbed block predicted what an inexact inner solve would do to a triangularly preconditioned saddle-point system: a two-step residual growing like the inner tolerance, a constant a few times the model's, and a step rule exact to one step on nine runs in ten. A real inner iteration under flexible GMRES delivers something else. Conjugate gradients stopped at a residual tolerance hands back errors ten to a billion times smaller than it was asked for, the outer residual follows that error with a slope near one and a constant ten to a hundred times the model's, the rule counts four runs in five — and the real solve still costs no more outer steps, while loosening it never once saved inner work.
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.
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.
The division that cannot be done
Conjugate gradients divides by pᵀAp at every step, and on a matrix that is not positive definite that number can be zero or negative. The guard against it has been here from the first essay and described it as a failure. In the method that made conjugate gradients famous it is the single most valuable object the iteration can produce, and it costs six matrix–vector products.
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.
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.
The step before the reset
On the strongly nonlinear problem, inexact Newton's second forcing rule took two more Newton steps than the first and half as much work again, and the blame went to its safeguard, which let the forcing term jump back to 0.9 when the residual rose. Capping that jump at ten times the last forcing term was predicted to remove the two steps and bring the rule within five per cent of the first. It removes the steps, at three targets of four. It saves 0.7 per cent of the work, and leaves the rule 45 per cent dearer than the first. The reset was the cheap part: four loose steps for 55 inner iterations. The cost was the step before it, solved to a forcing term of 0.024 for 109 iterations, where the first rule spent 5 — and on the ill-conditioned problem, where the residual never rose at all, the cap costs ten per cent.
The part a circulant can cancel
A separable kernel with a small isotropic part was preconditioned by the circulant sampled from the whole mixture's symbol. The cheaper choice keeps only the separable part's symbol and leaves the isotropy as error, and the prediction was that it widens the same treads by about the same amount — the same step count to a thousandth of isotropy — and falls behind past a hundredth. The step count is the same to within one on every grid up to ε = 10⁻³, and the cheaper preconditioner is behind on every grid from ε = 0.1. But it does not widen the same treads. It puts its error on the tread at one, where sixty-four of the hundred eigenvalues sit, widening it 7.6 times as fast as the mixture's symbol does, and it leaves the tread the mixture widens most nine times narrower. The counts agree because conjugate gradients pays for the widest tread's logarithm, not for which tread it is.
The residual the method reports
Conjugate gradients prints a relative residual of 6.9·10⁻²¹. The unit roundoff is 1.1·10⁻¹⁶, so that is not a small residual and not a large one — it is not a residual. The vector the method is holding at that step has ‖b − Ax‖/‖b‖ = 5.1·10⁻¹⁰, and nothing in the run says so.
The gap was the square
Eisenstat and Walker's second forcing rule was a third dearer than the first on a strongly nonlinear problem, and the cost had been traced to one over-tight step: its safeguard is skipped below 0.1, so the forcing term fell to 0.024 and the step took 109 inner iterations. Applying the safeguard always was predicted to hold that step at 0.04, halve its cost and bring the rule within fifteen per cent of the first. It holds the step at 0.038 and saves twenty iterations; the rule stays forty per cent dearer. The residual still rises after that step, because at that point Newton's own step overshoots and any solve tighter than about 0.06 reproduces it. A line search removes the rise and the reset and still leaves the second rule thirty-six per cent above the first. What is left is the rule itself: 0.9 times the square of the last residual ratio, which after every fast fall asks for a solve far tighter than the next step needs.
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.
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.
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.
A proof that does not ask how large the matrix is
Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n. The factorisation that settles the same question costs a third of n³, which grows by a factor of sixty-four over the same range.
A walk needs a length
The gap between the two residuals grows as the square root of something, and a square root needs a length. Two quantities are candidates — how far the iterates travelled and how many steps were taken — and only a second sweep separates them. Across a fourfold change in size the iteration count goes from 39 to 96 and the gap goes from 5.04·10⁻¹⁵ to 5.33·10⁻¹⁵.
The certificate that arrives soonest is worth least
The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth. At λₘᵢₙ = −10 the step arrives after two products and gets 39.6 per cent; at −10⁻³ the same two products get 89.8, and the whole sweep costs eight.
Named alongside it
The objects these essays reach for when they reach for this one.
PreconditioningStopping criterionCondition numberFilter factorsIterative regularisationResidualKrylov subspaceCirculant preconditionerSemi-convergenceTikhonov regularisationForward errorClustered spectrum