Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Argument principle — where it appears

A contour integral of a function's logarithmic derivative counts the zeros inside the contour, with multiplicity. For a matrix-valued function the same integral of tr(T⁻¹T′) counts eigenvalues, so a question with an integer answer becomes a quadrature.

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

Also named here as complex arithmetic — the same set of essays touches all of them, so they are one junction rather than several.

-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

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

Named alongside it

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

Complex arithmeticContour integralNonlinear eigenvalue problemQuadratureExact ground truthLambert wMatrix polynomialNewton iterationRandom probeRankTrace estimation

All concepts