Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Capacitance matrix — where it appears

The small dense matrix a low-rank correction formula has to solve, built by applying the base matrix's inverse to the correction's columns. Its size is the rank of the correction, and its condition number is how much of the base matrix's trouble the correction carries.

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

10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10³10⁵σ — how far the periodic wrap is from singularrelative forward error10⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷10⁻⁸10⁻⁹10⁻¹⁰10⁻¹¹10⁻¹²periodic correctionκ(C)·uelimination on Tn = 64, median of five answersperiodic correction, σ = 10⁻⁸1.2·10⁻⁴elimination on T, σ = 10⁻⁸1.1·10⁻¹⁴κ(C) at σ = 10⁻⁸4·10⁸κ(T) at σ = 10⁻⁸1712the same matrix T in every columnonly the wrap it is solved through changes

The circulant the problem did not contain

A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact. The accuracy claim is not. On tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the correction is wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination is right to 1.1·10⁻¹⁴ — because the periodic neighbour is singular at σ = 0, the two-by-two system inherits that, and the two amplifications multiply.

structure · Circulant -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.

structure · Circulant

Named alongside it

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

CancellationCirculant matrixCondition numberDiscrete laplacianForward errorNear-null spaceSymbolWoodbury identityInvariant subspaceIterative refinementLow-rank updateTwisted circulant

All concepts