Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Toeplitz — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 10¹10²10²size ncondition numberlimit 81measureda limit, as a fraction of itselfreached at n = 1280.99still to go0.011κ at n = 8, as a fraction0.52every point is below the line and none of them is on itthe limit is not a value

    A limit the matrix never reaches

    Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8. The 8×8 section reaches 52% of it, the 128×128 reaches 98.9%, and none of them ever arrives. A statement about a family is not a statement about the matrix in front of you.

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

    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.

    part 2 · structure
  3. 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%.

    part 3 · structure
  4. 357911110¹grid side meigenvalue of C⁻¹Awithin ½ of onethe cluster grows like the sidem = 4: inside of 169m = 6: inside of 3611m = 8: inside of 6413m = 10: inside of 10017the cluster grows with the sideand the spectrum with the area

    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.

    part 4 · structure
  5. change in the preconditioned countseparable, circulant, 0.5 → 0.980isotropic, circulant, 0.5 → 0.98190.50.60.70.80.910306090120150180correlation ρconjugate gradient stepsSeparable, no preconditionerSeparable, circulantIsotropic, no preconditionerIsotropic, circulantdashed: no preconditionerthe flat count belonged to the separable kernel

    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.

    part 5 · structure

All series