Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Balanced truncation — where it appears

Reduction of a model in the coordinates where every direction is equally reachable and observable, by dropping the least of them. Its error is bounded before the reduced model exists, and on ordinary problems the bound is attained rather than approached.

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

123456710⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹order r kepterror and bounds2Σσ, and the errorσᵣ₊₁a bound that is an equalityorders7bound ÷ error, worst1spread over the sweep1error ÷ σᵣ₊₁, worst2.1computed before the modeland attained by it

The bound that is known in advance

Almost every error on this site is measured after the fact. Balanced truncation has one that is computable before the reduced model exists, in a norm of a function rather than of a residual — and on ordinary problems it is not an upper bound that is loose. It is attained.

reduction · balanced truncation 1357911131510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1index kσₖ ÷ σ₁σ₁√utwo factorstheir productthe normal equations, againroutes agree to k =6product floors at9.7·10⁻¹⁰σ₁√u2.3·10⁻⁹κ(P)κ(Q)1.8·10³⁶√ of it1.3·10¹⁸do not form the productthe σ below the line are the bound

The product nobody had to form

The Hankel singular values are the square roots of the eigenvalues of PQ. Form that product and half of them stop existing, at a floor this site can predict from one number — and the fix is the one the least-squares field has had since its first essay, arriving in a place with no least-squares problem in it.

reduction · balanced truncation 10⁻¹110¹10²10³10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵s, on the real axis|H − Hᵣ| ÷ |H|exact where askedpoints4conditions bought8worst at a point5.3·10⁻¹⁶worst away from one8.4·10⁻⁴4 points, 8 conditionsand no bound in between

Exact at the points that were named

Balanced truncation asks for nothing and bounds everything, at a cost no large model can pay. The other kind of reduction asks for r numbers, costs r solves, is exact at every one of them — and bounds nothing anywhere else. That trade is the whole of large-scale model reduction.

reduction · moment matching 01234567891011121310⁻¹110¹10²10³iterationinterpolation point σa fixed point that is a conditionorder4iterations13σ against −λ(Aᵣ)2.8·10⁻¹²H₂ error4.3·10⁻⁵it stopped movingand the condition holds there

Interpolating at the model’s own poles

One choice of interpolation points is not arbitrary — the mirrored poles of the model about to be built. It is a fixed point rather than a guess, and when it is reached it beats a method costing O(n³) — by 0.4 per cent, which is the honest size of the whole contest.

reduction · moment matching

Named alongside it

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

Lyapunov equationTransfer functionA-priori boundCondition numberFlop countGramianHankel singular valuesHermite interpolationMoment matchingRational krylovSingular valuesExact ground truth

All concepts