Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

ADI iteration — where it appears

An iteration for a matrix equation that applies a sequence of shifted solves and produces a low-rank factor rather than the full solution. Its error after each step is exactly a rational function of the matrix, evaluated on the spectrum.

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

Also named here as equioscillation — the same set of essays touches all of them, so they are one junction rather than several.

1234567891010⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹kλₖ₊₁ ÷ λ₁, and the boundZ_k²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.

reduction · gramian decay 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.

reduction · gramian decay

Named alongside it

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

Condition numberEquioscillationGramianLow-rank approximationLyapunov equationRational approximationZolotarev numberHankel singular valuesShift selectionSingular values

All concepts