Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rational approximation — where it appears

Replacing a function by a ratio of polynomials, whose poles can be placed where the function is not analytic. Against an algebraic singularity it converges geometrically where a polynomial converges algebraically, and the poles are what buys the difference.

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

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.

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 23456710⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²poles in the approximantresiduals and errorforward error‖T(λ)x‖‖T̃(λ)x‖one extra evaluationagainst the approximant1.5·10⁻¹²against the problem asked1.9·10⁻⁶forward error4.8·10⁻⁵‖g − r‖ there8.5·10⁻⁵the free residual is flatand the answer is not

The problem the solver was actually given

A linearisation is exact — it has the polynomial's eigenvalues, with their multiplicities, and the whole loss is arithmetic. A nonlinear eigenvalue problem does not offer that. Every algorithm replaces the function first, and the term that replacement contributes is committed before any number is rounded and appears in no residual.

polynomial · Approximation before linearisation 110¹10⁻⁷10⁻⁵10⁻³distance from the branch point, λ + c|g − r|the eigenvaluesdegree 98 poleschosen, not computedreach0.06left end, from the cut0.2rational, worst8.5·10⁻⁴polynomial, worst0.0068linearisation size, both54committed before the solveand invisible to it

An error committed before the arithmetic

Before a nonlinear eigenvalue problem is solved, somebody says where they think the eigenvalues are. That sentence sets the accuracy of everything that follows by five orders, costs nothing to say, and cannot be revised once the approximation built on it is in hand.

polynomial · Approximation before linearisation 263850627410⁻⁵10⁻³10⁻¹rows in the linearisation‖g − r‖ on the target setpolynomialrationalequal cost, two basesreach0.06largest size drawn78rational there2·10⁻⁵polynomial there0.0015the ratio73no winner on an easy targetand two orders on a hard one

Two approximants and one matrix size

A polynomial approximant linearises to nd rows and a rational one to n(m+1), so the fair contest fixes the matrix and varies the basis. On an easy target set the two are indistinguishable and the ordering flips with the noise; on one that reaches a branch point the rational pulls away by two orders.

polynomial · Approximant choice -10123456789-101λbranch point at −0.4the closed formwhich of these is an answereigenvalues returned36wanted6past the branch point6complex24worst against the closed form7.7·10⁻⁴all of them exactfor a problem nobody asked

The eigenvalues that are answers to nothing

A rational approximant of degree five turns a six-by-six problem into a thirty-six-by-thirty-six one, and thirty-six numbers come back. Six are the answer. The rest are exact eigenvalues of the approximant, lying where the function it approximates is not a real number at all.

polynomial · Spurious spectrum 12345678910111210⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹degree of the approximantworst relative error on the target setchosen by the residualdegree reached12error there10⁻¹²even support, same degree1.1·10⁻⁷advantage702nearest support point0.096clustering ratio1.5filled: points chosen by the erroropen: points spread evenly

The points the algorithm chose

A rational approximant whose support points are picked by its own residual clusters geometrically at a branch point nobody named — recovering by measurement the rule a hand-built approximant is given. At degree ten it is seven hundred and fifty times more accurate than the same form with its points spread evenly.

polynomial · Adaptive interpolation eight polesorder 5: true ÷ σ₆/σ₁457order 5: true ÷ midpoints1.712345610⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹order of the modelerror, over the largest |H|true errorerror at the midpointsmisfit at the samplesσₖ₊₁ ÷ σ₁ of the pencildotted: where the arithmetic stopsthe singular value is optimistic

An error estimate made of samples

A Loewner model built from samples of a transfer function comes with no error bound, and the number every code reads to choose its order — the pencil's next singular value — is the obvious stand-in. On four systems sampled at 48 points it is the error of the order-k model for the first two orders, within a factor of 2.5, and then falls away from it by about a decade an order: by the fifth it is optimistic by 109, 181 and 457, and on one system by 6,700 at the sixth. An AAA fit of the same degree to the same samples has an error within a factor of six of the Loewner model's at every order, so the shortfall is not the projection's. The model's misfit at its own samples is optimistic the same way. What works is more samples: the error at the 47 midpoints between the samples is within a factor of 2.2 of the true error at every order on every system, and the four midpoints nearest the poles alone within a factor of three.

reduction · Data-driven realisation

Named alongside it

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

Approximation before linearisationCondition numberBranch pointLinearisationNonlinear eigenvalue problemZolotarev numberADI iterationData-driven realisationEquioscillationExact ground truthGramianLoewner matrix

All concepts