Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Clustered spectrum — where it appears

A spectrum with all but a few of its eigenvalues packed near one value, which is what makes a Krylov method converge in few steps.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

10²110¹10²size niterations to 10⁻¹⁰λ_min(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλ_min(C) at n = 16-0.4λ_min(C) at n = 32-0.14λ_min(C) at n = 640.016λ_min(C) at n = 1280.051λ_min(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

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.

structure · preconditioning 10²020406080100120140160size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.13‖C − T‖/‖T‖, wrapped0.25smallest eigenvalue, wrapped, n = 16-0.65one of them is positive definiteand it is the one that is nearer

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.

structure · toeplitz 10²020406080100120unknownsiterations2D, no preconditioner2D, preconditioned1D, preconditionedone construction, two dimensions2D steps at 16 unknowns102D steps at 100 unknowns211D steps at 100 unknowns10the same averaging, the same transformand a count that no longer stops growing

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%.

structure · toeplitz 024681012141618024681012141618distinct eigenvalues in the spectrumstep the recurrence stops atthe step is m, not nn = 30 throughoutspectra drawn8every one breaking at m8worst residual at the breakdown5.6·10⁻¹⁶smallest gain over the step before3.5·10¹⁰an invariant subspace contains the answerand its dimension is what the method costs

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.

iterative · breakdown

Named alongside it

The objects these essays reach for when they reach for this one.

Circulant preconditionerConjugate gradientsPreconditioningToeplitz matrixCondition numberConvergence rateDiscrete fourier transformPositive definiteArnoldiAsymptotic analysisCirculant matrixFinite termination

All concepts