Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Quadrature — where it appears

Approximating an integral by a weighted sum of values of the integrand. On a closed contour with an analytic integrand the trapezoidal rule is the right choice, because its error falls geometrically in the number of points rather than algebraically.

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

-2-101234-5-3-1135real partimaginary part4 insidea countable spectruminside the contour4drawn12existing∞worst branch residual1.6·10⁻¹⁵there is no last eigenvalueso the question has to change

A problem with infinitely many eigenvalues

Let the matrix depend on λ through something that is not a polynomial and three things stop being true at once. There is no linearisation, there is no characteristic polynomial, and "compute the spectrum" is not a request that can be granted — the only finite question is how many eigenvalues are inside this circle.

polynomial · Nonlinear eigenvalue 11.31.61.92.210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²log₁₀ quadrature pointsdistance from the true counthalf an eigenvaluean integer, eventuallytrue count2at 4 points2at 128 points2finest error1.4·10⁻¹³the integral is an integerand a rounding hides how far it was

The last digit is the cheapest

Every cost curve on this site has the same shape: the first digits are cheap and the last ones are not. One method inverts it. Doubling the work buys twice as many digits as the previous doubling did, so the price of a digit halves every time it is paid.

cost · Nonlinear cost 1216202428323640444810⁻¹110¹10²grid points nrelative error against the continuous signalbest truncation, 0.117best grid: n = 26best K = 28with noisenoise-freeno λ anywhere in this curvebest grid, error0.13best truncation, error0.12κ on the best grid61grid where it has doubled34every point is an unregularised solvethe grid chose the truncation

The grid was the first filter

A continuous deconvolution discretised on n points and solved with no regularisation at all is not unregularised. Its error against the continuous signal is least at 24, 26 and 34 points for noise of 1%, 0.1% and 0.01% per sample — beside best truncations of 24, 28 and 32 components on a 64-point grid — and within 4 to 16 per cent of their error. The grid's own filter factors sum to n exactly and fall through a half at k = n. Choosing the grid was choosing a truncation, before anybody chose a λ.

regularisation · Regularisation 11.31.61.92.210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²log₁₀ quadrature pointsdistance from the true counthalf an eigenvaluean integer, eventuallytrue count2at 4 points2at 128 points2finest error1.4·10⁻¹³the integral is an integerand a rounding hides how far it was

Counting what is inside a circle

A trace of a matrix nobody wants to form, integrated around a contour, gives an integer — how many eigenvalues are inside. It converges exponentially, it is estimated with random probes, and the probe block is a ceiling that the answer does not mention.

randomised · Trace estimation 123456024681012moments Krank of the block Hankel12 eigenvalues insidethe ceiling K·ℓthe ranka ceiling with a knob on itprobes2eigenvalues inside12rank at K = 12rank at K = 612solves, at every K512one ceiling per probeand K of them per moment

A ceiling with a knob on it

A contour method returns at most as many eigenvalues as its probe block has columns, and the object that comes back does not distinguish that from having found everything. One line of the derivation multiplies the ceiling by a number the caller chooses, and it costs no extra solves at all.

polynomial · Nonlinear eigenvalue 123456110²10⁴10⁶moments Kκ of the block Hankelintegrated in zin (z − c)/ρone division per pointradius6unscaled, K = 62.3·10⁶scaled, K = 61750the factor between1291the ceiling rises by Kand so did the conditioning

The conditioning that rises with the ceiling

Higher moments multiply a contour method's ceiling by K and grade its block Hankel over ρ to the 2K, so the two knobs are the same knob. One division per quadrature point separates them, and the measurement of what it is worth grows from twenty to twenty thousand.

polynomial · Nonlinear eigenvalue -6-4-20246-6-4-20246real partimaginary partan infinite spectrum, finitely askedinside the contour12probes4moments used3values returned24worst against the closed form6.2·10⁻¹⁵infinitely many eigenvaluesand a question with an answer

Where a contour's budget should go

A contour method's ceiling is the number of probes times the number of moments, and the moments are free in solves while the probes are not. Four ways of reaching one ceiling come out four orders apart, the ordering is not monotone, and what separates the best two is not the usual draw but the unlucky one.

polynomial · Nonlinear eigenvalue

Named alongside it

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

Contour integralNonlinear eigenvalue problemRankComplex arithmeticCondition numberContour eigensolverExact ground truthMomentNumerical rankArgument principleRandom probeTrace estimation

All concepts