Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Discrete fourier transform — where it appears

The change of basis that turns a circular convolution into a product, and a circulant matrix into a diagonal one.

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

024681012141610⁻¹1index kλthe transformthe eigensolverC = F* Λ F is a factorisationworst relative disagreement2.6·10⁻¹⁵‖Cx − b‖/‖b‖ from the transform solve4.7·10⁻¹⁶imaginary part of a real spectrum1.2·10⁻¹⁶n = 16, and the whole matrix is 16 numberseigenvectors known in advance

The matrix that is one row

A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly. An eigensolver spends a sweep of Jacobi rotations over 256 entries arriving at the same answer, and agrees to 1.2·10⁻¹⁵.

structure · circulant 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²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

Named alongside it

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

Circulant matrixCondition numberToeplitz matrixAsymptotic analysisCirculant preconditionerClustered spectrumConjugate gradientsPreconditioningSymbolEigenvaluesExact inverseFactorisation

All concepts