Clustered spectrum — where it appears
Named by 12 essays across 4 fields — each of them below, with the objects they name alongside it.
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 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.
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.
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.
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 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 circle between two eigenvalues
A contour count's error is not approximately governed by the nearest eigenvalue; it is exactly one closed-form term per eigenvalue, and summing those terms reproduces the quadrature to a millionth at 1,720 radius and point pairs. Three things follow. The rate is the ratio of the two moduli the circle sits between, not a distance, so two circles 0.2 from their nearest eigenvalue converge three times apart. Ten digits cost about 21 points divided by log₁₀ of that ratio, 71 points with twelve eigenvalues inside and 3,476 with six. And the best circle is not halfway: at the geometric mean of two eigenvalues on one ray their two terms are equal and opposite, and ten digits cost 27 points where the midpoint needs 84.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Conjugate gradientsPreconditioningCirculant preconditionerToeplitz matrixCondition numberKronecker productSeparabilitySymbolAsymptotic analysisConvergence rateCirculant matrixDiscrete fourier transform