Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sherman morrison woodbury — where it appears

The formula for the inverse of a matrix changed by a low-rank term: solve with the original matrix, then correct through a small system whose size is the rank. It turns a solve with a nearly structured matrix into solves with the structured one and a capacitance matrix.

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

at σ = 10⁻⁸Cramer's rule1.2·10⁻⁴pivoted2.9·10⁻¹⁰elimination on T1.1·10⁻¹⁴cancellation × u1.7·10⁻¹⁰-10-9-8-7-6-5-4-3-210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1σ, as a power of tenforward errorCramer's rulepivotedcancellation × uelimination on Tleft: σ small, the wrap nearly singularthe pivoted solve follows the cancellation

The correction lost to its own two-by-two solve

Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair. Both measurements solved the two-by-two correction system by Cramer's rule. Solved with a row interchange, the corrected solve on the same matrix loses 2.9·10⁻¹⁰ — the cancellation, and nothing multiplied onto it — and the single landing costs what the pair costs. The loss was in the determinant.

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.

Backward errorCapacitance matrixCirculant matrixCondition numberLow-rank updateSymbolFast fourier transformIterative refinementCramers ruleDeterminant

All concepts