Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rational krylov — where it appears

A subspace spanned by solves with the matrix shifted by several different numbers rather than by powers of one matrix. Spending the solves at different points keeps the basis independent where repeating one point does not.

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

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 2345678110²10⁴10⁶10⁸10¹⁰vectors in the basisκ₂ of the basisas derivedsolves spread outone subspace, two spanning setseight moments at one point7.7·10⁹eight points, spread1growth per vector661/u4.5·10¹⁵the same subspaceand only one of them usable

A basis that is the same subspace and not the same thing

The interpolation conditions are conditions on a subspace, so any basis of it will do. The one a derivation writes down reaches a condition number of 7.7·10⁹ by its eighth vector, and the rate at which it gets there is set by a number the user chose with no information.

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 10⁻¹110¹10²-45-35-25-15-551525s, the smallest of the three interpolation pointsrightmost pole of the reduced modelunstable above this linebalanced truncation, order 3exact, and unusablefull system's pole-3.5placements swept19unstable models4worst pole24their interpolation1.3·10⁻¹⁴balanced truncation-0.84the conditions all holdand the model cannot be run

A model that cannot be run

A stable system, reduced by matching its transfer function at three points exactly, comes back with a pole in the right half plane at four of nineteen placements — and matches at all three points to 1.3·10⁻¹⁴ while doing it. The construction did what it promised.

reduction · Reduced stability 10⁻¹110¹10²s, the smallest interpolation pointrightmost pole of the reduced model−10−10+1+10unstable above zeronumerical range edge, -0.986system's abscissa, -3.49two-sided, order 3one-sided, order 3one-sided, order 6Pe 10, nineteen placementssystem's rightmost eigenvalue-3.5edge of the numerical range-0.99two-sided, order 3: unstable placements4one-sided, order 3: unstable placements0one-sided, order 6: unstable placements0signed logarithmic axisshaded: poles in the right half plane

Half the conditions and a certificate

A two-sided interpolatory reduction of a stable convection–diffusion system came back unstable at four placements of nineteen. The one-sided reduction built from the same kind of solves came back stable at all 152 placements measured across eight Péclet numbers, and not by luck: every pole of a Galerkin model lies inside the numerical range of the operator, whose edge here is exactly the diffusion term's largest eigenvalue, −0.986 at Péclet 10. The price is the slope conditions, and spent as six one-sided shifts instead of three two-sided ones it beats the stable two-sided model at seven placements of ten.

reduction · Reduced stability Péclet 100, orders 1, 2, 3, 6nodal edge at 1,000, outflow8.9weighted edge at 1,000-0.097unstable nodal models7110¹10²10³-20246810largest cell over smallestright edge of the numerical rangenodal, small cells at the outflownodal, small cells at the inflowcell-size weightedabove the dashed line the certificate is goneit is a sufficient condition, not a failure

The inner product the mesh already computed

A Galerkin reduced model is certified stable when the operator's numerical range sits in the left half plane, and the certificate belongs to the coordinates. The coordinates that broke it before were a constructed rescaling. Grade a convection–diffusion mesh towards its outflow boundary layer — the grading anyone resolving the layer would choose — and nodal values break it too: the range's edge is past zero at a ratio of ten and reaches +8.9 at a thousand, and at Péclet 100 seven reduced models come back unstable. Weight the projection by the cell sizes the discretisation already computed and every model at every grading is stable, with the range's edge back at −0.098.

reduction · Reduced stability

Named alongside it

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

Moment matchingPetrov–GalerkinTransfer functionBalanced truncationConvection diffusionNon-normalityReduced stabilityCondition numberFlop countGalerkin projectionHermite interpolationKrylov subspace

All concepts