Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sturm sequence — where it appears

A recurrence over the leading principal minors of a symmetric tridiagonal matrix, whose sign changes count how many eigenvalues lie below a given shift. Each term costs one division and no square root, so the whole count runs in exact rational arithmetic with nothing rounded, and bisecting on the shift returns any eigenvalue to as many bits of its own size as are asked for.

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

1234567810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, largest firstrelative errorone-sided Jacobizero-shift QRshifted QReigenvalues of BᵀBagainst a rational bisectionσ_min, exactly2.1·10⁻³⁰worst, one-sided Jacobi4.4·10⁻¹⁶worst, zero-shift QR2.2·10⁻¹⁶worst, eigenvalues of BᵀB1a relative error is a ratioand the denominator is the answer

Small compared to what

This site's own singular value routine has carried a sentence since the month it was written — that one-sided Jacobi computes the small singular values to high relative accuracy and the standard method does not. It has never been measured here, because measuring it needs a σ that is known rather than computed. A bidiagonal matrix and a Sturm count in exact rationals supply one.

spectra · Relative accuracy 0102030405010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷decades of gradingworst relative errorthe answer is gonevia BᵀBone-sided Jacobizero-shift QRone axis, four routesBᵀB at the narrowest grading3.6·10⁻¹⁴and at the widest1.9·10⁷Jacobi, worst over the sweep1.5·10⁻¹⁵zero shift, worst1.1·10⁻¹⁵the definition is not a methodand squaring buries what it squares

A threshold the matrix does not set

Two numbers come out of a relative-accuracy comparison and they belong to different things. The size of the matrix moves the constant of the routes that never fail, by a factor of 2.7 between n = 4 and n = 10; it does not move the point where the route through BᵀB stops returning an answer, which sits between ten and eleven decades of grading at every size drawn.

spectra · Relative accuracy

Named alongside it

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

Bidiagonal matrixCondition squaringExact arithmeticGraded matrixJacobi's eigenvalue methodRelative accuracySingular valuesCancellationCondition numberUnit roundoff

All concepts