Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Random probe — where it appears

A block of random vectors a method multiplies a matrix or a resolvent against, standing in for a whole space it cannot afford to sweep. The number of columns caps how many directions the result can carry, and the size of each direction's component in the block decides how visible it is, so the answer moves with the draw.

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

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 -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 problemQuadratureRankArgument principleComplex arithmeticCondition numberContour eigensolverExact ground truthMomentNumerical rankTrace estimation

All concepts