Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Gramian decay — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 1234567891010⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹kλₖ₊₁ ÷ λ₁, and the boundZₖ²the Gramianpredicted from two numbersstates30κ of the spectrum389λ11 ÷ λ₁2.5·10⁻⁸the bound there5.2·10⁻⁴the cliff everything rests onand the reason for it

    Why a Gramian can be truncated at all

    Every method in this field rests on one fact nobody states the reason for — the eigenvalues of a Gramian fall off a cliff. The equation defining it has a rank-one right-hand side and no low-rank structure anywhere — and the answer's decay is a rational approximation problem with a closed-form rate.

    part 1 · reduction
  2. 10¹10²10³10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹λ, over the spectrum of −A|r(λ)|geometric maxequally spacedgeometricone line of codeshifts6κ of the spectrum389geometric max0.12equally spaced max0.89the factor between7.5the same k solvesand one choice of where

    Where to put the poles of a rational function

    Three times in one field the same question arrives from different directions — ADI shifts, rational approximation of a square root, the decay of a Gramian — and it has one answer. Cluster them geometrically towards wherever the function is difficult, and the alternative that looks reasonable costs orders.

    part 2 · reduction
  3. 234567891010⁻⁴10⁻²1ADI steps krelative error, and max|r|²max|r|²the measured errora bound that is an identitysteps drawn9ratio, worst0.77spread of the ratio1error at k = 103.9·10⁻⁴its residual1.1·10⁻⁴four orders of errorand one constant

    Bracketing an error nobody can measure

    The error of a low-rank Gramian factor is the one quantity a caller cannot compute, because computing it needs the Gramian the factor exists to avoid forming. Two numbers that can be computed sit either side of it — a rational factor known before the run, and a residual known after — and they stay a factor of four apart across a fourfold change of size.

    part 3 · reduction

All series