Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Toeplitz matrix — where it appears

2 essays name this object, across one field. What follows is each of them, and the objects they name alongside it.
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.

structure · toeplitz 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

Named alongside it

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

Condition numberAsymptotic analysisCirculant matrixCirculant preconditionerClustered spectrumConjugate gradientsConvergence rateDiscrete fourier transformExact inversePositive definitePreconditioningSymbol

All concepts