Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

A-priori bound — where it appears

A bound on an error that can be computed before the computation it bounds is performed. Almost none of them are tight, which is what makes the one balanced truncation carries unusual: on ordinary problems it is attained.

Named by 9 essays across 3 fields — 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 in numerical linear algebra 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 10²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹κ of the sumrelative sizethe boundκ · umeasured spreadtwo curves and one constantspread ÷ κu, low0.25spread ÷ κu, high0.26bound ÷ spread, low7932decades swept10the spread is computablethe bound cannot see the order

A bound every answer satisfies

The classical bound on a summation error is correct, it covers all twenty-six answers one vector produced, and it is 7,932 times larger than the difference between them. A statement true of every ordering cannot say which ordering you got.

machine · Reduction order 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 ‖H − Hₙ₋₁‖∞ ÷ σₙpositive residues2.0000mixed residues2.0000clustered poles2.0000four poles2.0000wide spectrum2.0000‖ΔH‖ 3.89·10⁻⁴ σ 1.94·10⁻⁴‖ΔH‖ 3.92·10⁻⁴ σ 1.96·10⁻⁴‖ΔH‖ 0.00502 σ 0.00251‖ΔH‖ 8.41·10⁻⁴ σ 4.21·10⁻⁴‖ΔH‖ 4.6·10⁻⁴ σ 2.3·10⁻⁴2four systems, four ratios, one number: 2.0000one state, one equalityand the sum is that, repeated

The state that is removed is not a mode

Balanced truncation removes one state and pays exactly twice one Hankel singular value. The natural reading is that the state removed is the model's least important mode and that the σ is that mode's own size — and on five systems that reading over-estimates by between 1.21 and 7.46, never once under.

reduction · Balanced truncation 11.31.610⁻¹110¹10²10³log₁₀ ntropical root ÷ actual modulusexactsmallest moduluslargest modulusthree norms, two endslarge root, n = 40.96large root, n = 320.94small root, n = 45.4small root, n = 32230a maximum predicts a maximumand says nothing about a minimum

An estimate that does not move

The tropical roots are said to miss the bottom of a spectrum by a factor growing like n². The estimate does not get worse. It changes by four per cent between four masses and sixty-four while the modulus it names falls by a factor of a hundred and sixty, and an estimate that is constant in the variable the answer depends on is a different defect from an inaccurate one.

polynomial · Polynomial scaling ζ = 0.03largest over-statement4.8removing one state1123456789101112345order keptbound ÷ measured errordashed: the bound attaineda mode that rings is not a heat mode

A mode that rings is counted twice

Balanced truncation's bound, twice the sum of the discarded Hankel singular values, was attained at every order on the heat model — a formula for the error rather than a bound on it. On six lightly damped oscillators it is loose at every order but the last, by factors between 1.3 and 5, at every damping from 0.7 to 0.01. The reason is visible in the singular values: a mode that rings contributes two of them, nearly equal, and removing the mode costs about what removing one would. The last mode's bound over its error is 2.02, 2.00 as the damping falls to 0.03 and 0.01. The equality was a property of modes with one singular value each.

reduction · Balanced truncation the pair's two σ added: distance from oneworst, damping to 0.050.053worst at a resonance, damping 0.10.160.40.60.811.21.41.61.8damping ratioreading ÷ measured error0.0050.010.030.10.3order 2order 4order 6order 8order 10shaded: within ten per centa pair costs its two σ, until the modes overlap

Where a ringing mode stops being a pair

A lightly damped mode puts two nearly equal Hankel singular values into balanced truncation, and the reduction error was read as twice the larger of the first pair cut — right to two per cent at damping 0.01, wrong by half at 0.1. Read instead as the pair's two values added, the error is right to within six per cent at every order up to damping 0.05, and the pair's split turns out to be twice the damping. What it cannot do is say when the reading fails. The split predicts nothing: the widest split at damping 0.1 has the best reading. The failures come from somewhere the pair does not look — the other dropped modes' response under the peak, and a cut between two singular values that agree to under one per cent, which left a reduced model with a pole a thousand times closer to the axis than any pole of the system it came from.

reduction · Balanced truncation small group, worst backward errorleading, at 4·10¹¹2.7·10⁻⁷flv, at 4·10¹¹7.1·10⁻⁷tropical, at 4·10¹¹10⁻⁵trailing, at 4·10¹¹7.1·10⁻¹⁶both, at 4·10¹¹7.1·10⁻¹⁶10¹10⁵10⁹10¹³10¹⁷10²¹10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²separation ‖C‖²/(‖M‖‖K‖)backward errorleading reductionleading, FLV scalingleading, tropical scalingstrailing reductionboth reductionsdotted grey: u times the separationonly the trailing reduction keeps the small group

Two groups need two reductions

When a quadratic eigenproblem's tropical roots are far apart its eigenvalues fall into two groups, and the remedy offered is a second scaling — one per tropical root, each run keeping the group its root predicts. Raise the damping on an eight-mass chain until the roots are 10²³ apart and measure every eigenvalue: no scaling rescues the small group. Its backward error grows as the unit roundoff times the separation under Fan–Lin–Van Dooren's scaling, under both tropical scalings and under none, to 10⁻⁵ at a separation of 4·10¹¹. What rescues it is the other reduction of the same pencil — inverting the constant term instead of the leading one — which keeps the small group at rounding at every separation and loses the large one instead. Both reductions, each keeping its own group, give all sixteen eigenvalues to 10⁻¹¹ at worst. On the way, the closed form that served as the exact answer turned out to lose the small roots to cancellation, from the same separation.

polynomial · Polynomial scaling the censusreductions1452ties431doubled, all ties1010⁻³10⁻²10⁻¹110¹10²0.511.52gap at the cut ÷ smaller neighbouring gaperror ÷ twice the first dropped σdoubled abovetiesshaded: gap under a fifth of its neighboursevery doubled error is at a tie

A tie is a gap smaller than its neighbours

A balanced truncation that cut between two Hankel singular values agreeing to under one per cent left a reduced model with a pole near the axis and twice the error the σ promised, and the warning drawn from it was a rule: never cut inside a tie. Over 1,452 reductions of twelve oscillators, all ten doubled errors are at ties — but three of them have gaps of about two per cent, which a one-per-cent rule lets through, and what they share is a gap under a fifth of the gaps beside it. Moving every such cut one order down never doubles and halves each doubled error, for a median cost of one per cent. It is not free everywhere: at damping 0.5 it costs up to two and a half times. And the near-integrator was never the harm: 32 reductions have one and 22 of them read their σ correctly. The cheapest test of all is one evaluation of the error at zero frequency, which picks out the ten doubled cuts and nothing else.

reduction · Balanced truncation

Named alongside it

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

Balanced truncationTransfer functionHankel singular valuesLyapunov equationGramianExact ground truthHinf normAsymptotic analysisFrobenius normMatrix polynomialMcMillan degreeQuadratic eigenvalue problem

All concepts