Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Twisted circulant — where it appears

A matrix like a circulant except that the wrapped-around corner entries are multiplied by a unit complex number, so its eigenvectors are shifted Fourier modes. The twist moves where the symbol is sampled, which lets a fast Fourier solve avoid a zero of the symbol.

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

-7-6-5-4-3-210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110²10⁴log₁₀ of the twist's distance from landing, in turnsrelative forward errorsimple zero, landed on at 0simple zero, landed on at 0.3double zero, d = 2n = 64, twist 10⁻⁵ of a turn from landingpair: error, κ(A) = 4.1·10⁶5.4·10⁻¹²single: error, κ(A) = 3.8·10⁶3·10⁻⁸double: error, κ(A) = 4.2·10¹²7515the same condition number of the wrapa different number of modes near zero

Two near-zeros cost less than one

Solve a well-conditioned tridiagonal matrix through a nearly singular wrap and the correction's accuracy is not set by how singular the wrap is. At κ = 4·10⁷ one wrap returns the answer to 8.8·10⁻¹¹ — better than κ·u — and another, at κ = 3.8·10⁷, returns it to 3.3·10⁻⁶. The difference is how many of its samples sit near the symbol's zeros. A real wrap lands on a conjugate pair, a rank-two correction absorbs the pair exactly, and its two-by-two system has condition number 1.00 — which mattered because that system was solved by Cramer's rule; solved with pivoting, the single landing costs what the pair costs.

structure · Circulant size n163264128(L + s)²1 stepκu 1.2·10⁻¹²1 stepκu 1.9·10⁻¹¹1 stepκu 3.1·10⁻¹⁰1 stepκu 4.9·10⁻⁹(L + s)³1 stepκu 1.2·10⁻¹⁰1 stepκu 7.9·10⁻⁹1 stepκu 5.1·10⁻⁷1 stepκu 3.2·10⁻⁵(L + s)⁴1 stepκu 1.3·10⁻⁸1 stepκu 3.3·10⁻⁶2 stepsκu 8.4·10⁻⁴no first solveκu 2.2·10⁻¹(L + s)⁵3 stepsκu 1.3·10⁻⁶3 stepsκu 1.4·10⁻³no first solveκu 1.4·10⁰no first solveκu 1.4·10³(L + s)⁶3 stepsκu 1.3·10⁻⁴no first solveκu 5.6·10⁻¹no first solveκu 2.3·10³no first solveκu 9.5·10⁶κu: the wrap's condition number times the unit roundoffsteps are not a function of κu

Where one step stops being enough

One step of iterative refinement took the squared Laplacian's circulant-wrap solve to elimination's accuracy at every size, and the account was that each step multiplies the error by the wrap's condition number times the rounding, so one step suffices while that product is small. Raised to higher powers, the band tests the account and half of it holds: each step does contract by about κ(wrap)·u. The other half fails. The fifth power at sixteen points needs three steps with κ(wrap)·u near 10⁻⁶, where the third power at 128 points needs one with thirty times more, because the first solve starts up to a thousand times further from the answer than κ(wrap)·u says.

structure · Circulant

Named alongside it

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

Capacitance matrixCirculant matrixSymbolWoodbury identityCancellationCondition numberDiscrete laplacianForward errorInvariant subspaceIterative refinementNear-null spaceToeplitz matrix

All concepts