Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Shift selection — where it appears

Choosing the points at which a method takes shifted solves, whether as ADI shifts, interpolation points or the poles of an approximant. It costs nothing to decide and is worth orders, and the answer is nearly always geometric clustering towards wherever the problem is difficult.

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

10¹10²10³10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹λ, over the spectrum of −A|r(λ)|geometric maxequally spacedgeometricone line of codeshifts6κ of the spectrum389geometric max0.12equally spaced max0.89the factor between7.5the same k solvesand one choice of where

Where to put the poles of a rational function

Three times in one field the same question arrives from different directions — ADI shifts, rational approximation of a square root, the decay of a Gramian — and it has one answer. Cluster them geometrically towards wherever the function is difficult, and the alternative that looks reasonable costs orders.

reduction · Gramian decay 110¹10⁻⁷10⁻⁵10⁻³distance from the branch point, λ + c|g − r|the eigenvaluesdegree 98 poleschosen, not computedreach0.06left end, from the cut0.2rational, worst8.5·10⁻⁴polynomial, worst0.0068linearisation size, both54committed before the solveand invisible to it

An error committed before the arithmetic

Before a nonlinear eigenvalue problem is solved, somebody says where they think the eigenvalues are. That sentence sets the accuracy of everything that follows by five orders, costs nothing to say, and cannot be revised once the approximation built on it is in hand.

polynomial · Approximation before linearisation thirty matricesBunch–Kaufman: unpushed, usable on12bounded (rook): unpushed, usable on511.251.51.7522.252.5051015202530push: the pivot multiplied bymatrices on which it is nearest the smallest eigenvalueBunch–Kaufmanbounded (rook)dashed: all thirtyno small push is reliable

The push a pivot needs belongs to the matrix

An indefinite factorisation's most negative pivot looks like an estimate of the most negative eigenvalue, and on one planted family Bunch–Kaufman's, pushed a tenth further, was a usable shift for inverse iteration. On thirty random symmetric matrices neither rule's pivot is: unpushed it is nearest the smallest eigenvalue on 12 and 5 of them, pushed a tenth on 13 and 9, and only a push of two serves 29. The push each matrix needs runs from 0.59 to 2.27 for Bunch–Kaufman — whose pivot is more negative than every eigenvalue on eight matrices and under half the smallest on others — and from 0.85 to 2.01 for the bounded rule. What does work needs no push at all: multiply the shift by a quarter until the factorisation of A − σI has no negative pivot, which Sylvester's law says is exactly when σ is below the spectrum. It lands every time, in a median of two or three factorisations.

elimination · Cholesky

Named alongside it

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

Condition numberRational approximationZolotarev numberADI iterationApproximation before linearisationBranch pointBunch–KaufmanEquioscillationGramianInertiaInverse iterationLanczos algorithm

All concepts