Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Jacobian — where it appears

The matrix of first derivatives of a vector-valued function, which a solver needs only as a product with a vector.

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

11.522.511.52xyexactly one roota verdict, not a bound‖I − C F′(X)‖0.28width of X0.8width of K(X)0.23strictly inside is a proofand overlapping is nothing at all

Proving the answer is in the box

Every other method here computes a number and estimates how wrong it is. This one returns a verdict: there is exactly one solution in this box, or there is none, or — the honest third outcome — nothing can be said. Two of the three are proofs about infinitely many points from finitely many operations.

arithmetic · interval 10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1εrelative error in J(x)vforwardcentralcancellationtruncationagainst a derivative that is exactforward floor1.3·10⁻¹⁰central floor1.1·10⁻¹²truncation slope, forward1truncation slope, central2no ε reaches the roundoffand the analytic derivative is free of the choice

An operator with no entries

At the sizes where linear algebra is expensive the matrix does not exist. What exists is a subroutine that returns Av. Every Krylov method survives that unchanged; every algorithm that reads an entry disappears. And the derivative such a code computes is accurate to ten digits instead of sixteen, which turns out to cost nothing at all.

iterative · matrix free

Named alongside it

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

Newton iterationCancellationDirected roundingExistence and uniquenessFinite differenceIncomplete factorisationInterval arithmeticKrawczyk operatorKrylov subspaceMatrix-freePreconditioningSparsity

All concepts