Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Asymptotic analysis — where it appears

A statement about how a quantity behaves as a size grows without bound, which need not describe any size that is actually run.

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

Also named here as symbol — the same set of essays touches all of them, so they are one junction rather than several.

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²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

Named alongside it

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

Condition numberDiscrete fourier transformSymbolToeplitz matrixCirculant matrixCirculant preconditionerClustered spectrumConjugate gradientsExact inversePreconditioningSzego theorem

All concepts