Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Fast fourier transform — where it appears

An algorithm that multiplies by the discrete Fourier matrix in order n log n operations rather than n². It diagonalises every circulant matrix at once, which is why a circulant system can be solved by two transforms and n divisions.

Named by 3 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 n = 64, twist of half a stepnearest sample, Laplacian0.0024nearest sample, squared5.8·10⁻⁶κ(wrap), squared2.8·10⁶10⁻³10⁻²10⁻¹110⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹θsymbolπ/nLaplacian, θ² near 0its square, θ⁴ near 0no twist puts a sample further than π/n from θ = 0and the symbol's order decides what it sees there

A zero no twist can step around

Solved through its circulant wrap with the small capacitance system factorised stably, a banded matrix was found to lose only what the cancellation in the correction costs, and a twist of half a step kept that cancellation near one. That holds only while the cancellation is large. With it kept small, the corrected solve's error is a quarter of the wrap's condition number times u on every case measured — and on a symbol with a zero of fourth order, the square of the Laplacian, no twist can keep the wrap well conditioned, because the nearest sample any twist can reach sees (π/n)⁴. At n = 64 the corrected solve is 34 times less accurate than elimination, where the Laplacian's is four.

structure · Circulant at n = 128refined ÷ elimination, n = 1281.4unrefined ÷ elimination3310²10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸matrix size nrelative errorκ(wrap)·ucorrectedeliminationafter one stepthe wrap grows as n⁴ and so does the corrected errorone step puts it on elimination's line

One step past the zero

The squared Laplacian, solved through its twisted circulant and a rank-four correction, lost 6 to 34 times more accuracy than elimination, because its symbol's fourth-order zero keeps the wrap as ill conditioned as the matrix whatever the twist. One step of iterative refinement — a residual formed with the band itself, a second solve by the same route — takes it to 0.59, 0.68, 0.73 and 1.40 times elimination's error at n = 16, 32, 64 and 128, and the second and third steps go no lower. The loss the zero imposed was the solver's, and a solver's loss is what refinement removes.

structure · Circulant

Named alongside it

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

Circulant matrixCondition numberBackward errorCapacitance matrixLow-rank updateSherman morrison woodburySymbolDiscrete fourier transformEigenvaluesFactorisationIterative refinementMatrix structure

All concepts