Preconditioning — where it appears
Named by 43 essays across 12 fields — each of them below, with the objects they name alongside it.
The problem that arrives again
A hundred and thirty essays have solved a system once and measured how wrong the answer was. Almost no computation is shaped like that. A solve is one step of an outer loop, its answer is an input rather than a deliverable, and four quantities treated here as accuracy requirements turn out to be assets with a shelf life.
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 solve that is d decompositions
A Kronecker sum is closed under nothing useful — its inverse is not a Kronecker sum and no factorisation of it is one. What it has instead is eigenvectors that are Kronecker products, so a solve with 1,728 unknowns takes one decomposition of a 12 × 12 matrix and nothing else.
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.
Three eigenvalues, and two are the golden ratio
Precondition a saddle-point system by the block diagonal of its own two definite pieces and the preconditioned matrix has exactly three distinct eigenvalues — 1, and the two roots of λ² − λ − 1. A minimal polynomial of degree three means three steps, at every conditioning, and the preconditioner nobody can afford turns out to be the statement the affordable ones are measured against.
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.
A preconditioner that need not know the constraint
Keep the constraint block exactly and replace the objective block by anything positive definite on the null space. The preconditioned matrix then has 2m eigenvalues at exactly one, and its remaining n − m are the generalised eigenvalues of a pencil in which the constraint does not appear. Sweep its condition number over six decades and they do not move in six digits.
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.
The sketch that is not the answer
Sketch-and-solve throws away the original problem and keeps the small one's answer, which is why its answer moves with the seed. Use the same sketch as a preconditioner instead and the condition number the iteration sees is the same number at every κ from a hundred to ten billion — identically the same, to nine digits, because the spectrum cancels out of it.
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%.
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.
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.
One eigenvalue and two steps
Put the off-diagonal block back into a block-diagonal saddle-point preconditioner and every eigenvalue of the preconditioned matrix becomes exactly one. GMRES still needs two steps, because the matrix is the identity plus a nilpotent part of norm 54, and a computed eigenvalue at one comes back as a ring of radius 8·10⁻⁸ — the square root of the rounding, not the rounding. With an approximate Schur complement the triangular form leaves one copy of each value where the diagonal form leaves two, and the step count halves.
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.
What survives one step of the barrier
An interior-point method solves the same system dozens of times with the same pattern and different numbers, and exactly p entries change between one step and the next. The pattern is reusable for ever. The factorisation is reusable for none of them, and the threshold that says so is a reduction factor of about a per cent against schedules that use ten.
The zero you are allowed to write
A deflation criterion sets a subdiagonal entry to zero because it is small. A drop tolerance discards an entry of a factor because it is small. A truncation discards a singular value because it is small. Three fields, three vocabularies, no shared arithmetic — and plotted as work saved against error accepted, one curve.
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 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.
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.
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 knob that moved two things
Decide how many digits the answer needs, divide by the condition number, and compress to that. It is the one rule licensed in advance here, and its two factors are not the independent inputs it reads as: the partition's leaf moves neither of them and moves the answer by nearly a factor of three, and the only knob here that raises κ halves the ranks while it does so.
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 order a batch arrives in
Sixteen problems over a parameter, solved in the order the loop produced them, cost a median of 1.54 times what the same sixteen cost sorted, and 2.80 times at the worst shuffling. A nearest-neighbour path computed from the parameter values alone recovers the sorted cost exactly, at every drift and every shuffle.
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.
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.
A preconditioner that is a tree
Every eigenvalue of a tree-preconditioned Laplacian is at least one and at most the total stretch — a combinatorial integer with no arithmetic in it. Measured, the bound is two to four times loose, and on a grid the preconditioner makes the conditioning worse by a factor of 1.85 at every size.
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 α.
A tolerance is priced by the problem
Three tolerances from three fields sit on one pair of axes and agree to within a factor of 5.74. That factor is the ratio of the two curves that cannot move. Change the only problem in the comparison and the third curve's fitted slope swings from 0.188 to 0.040 while the printed spread does not shift by a digit.
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 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.
An operator with no entries
At the sizes where linear algebra is expensive the matrix does not exist. What exists is a subroutine that returns Av. Every Krylov method survives that unchanged; every algorithm that reads an entry disappears. And the derivative such a code computes is accurate to ten digits instead of sixteen, which turns out to cost nothing at all.
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.
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 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 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 slopes were in the symbols
A separable BTTB kernel with a small isotropic part ε, preconditioned by the separable part's symbol circulant alone, has sixty-four eigenvalues at one that spread as ε grows — 13 times ε wide and shifted 7.7 times ε — while the mixture's own symbol spreads them only 1.7 times ε. Both slopes were predicted to follow, to five per cent, from first-order perturbation of that sixty-four-dimensional eigenspace: the shift as the mean of the perturbation's eigenvalues on it, the width as their spread. The widths come out at 13.372 and 1.732, matching the measurements to four digits. The shift does not come out as the mean, which is 5.77; it comes out as the midpoint of the extremes, 7.671, because that is what the measurement reads. And the decomposition says what the cheap preconditioner costs: the circulant part of the isotropic correction, which the separable symbol leaves in, carries ninety-nine per cent of its width. What looked like first order failing at a hundredth was the tread's centre moving, not its eigenvalues.
Named alongside it
The objects these essays reach for when they reach for this one.
Conjugate gradientsCondition numberCirculant preconditionerClustered spectrumToeplitz matrixStopping criterionFlop countIterative regularisationKronecker productResidualSeparabilityTikhonov regularisation