Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Complex arithmetic — where it appears

Arithmetic on numbers with a real and an imaginary part, which a real linear algebra library reaches by embedding. A complex system of size n is a real one of size 2n with the two parts stacked, so the embedding doubles the size and changes nothing else.

Named by 3 essays across 2 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

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

Named alongside it

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

Contour integralNonlinear eigenvalue problemQuadratureArgument principleExact ground truthRankContour eigensolverLambert wMatrix polynomialMomentNewton iterationNumerical rank

All concepts