Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

arrowhead-model

One function in the thick library, called 6 times across 6 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 8 claims it put to the test while drawing them, and where it stands against the rule this site is named for.

At its defaults it draws the projected matrix, against the basis it is supposed to project onto. Three quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 4.23·10⁻⁶ after. The basis's own orthogonality error stays at 9·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 2.5·10⁻¹⁵.

arrowhead-model is one function in lib/figures/thick.js — keeping the vectors — a third of the products, and the bound that stops bounding. Everything below came out of it during this build, at arguments taken from the essays rather than invented for this page. A figure here is the figure a reader meets in an essay, and if the generator changes, this page changes with it.

At its defaults

Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.

The projected matrix, against the basis it is supposed to project ontoThree quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 4.23·10⁻⁶ after. The basis's own orthogonality error stays at 9·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 2.5·10⁻¹⁵.1234567810⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³cyclerelative sizea vector kept twice‖T − QᵀAQ‖‖QᵀQ − I‖border recomputedwhich model is wrong‖T − QᵀAQ‖ at cycle 21.1·10⁻¹⁵at cycle 34.2·10⁻⁶‖QᵀQ − I‖, worst9·10⁻¹⁶the basis is orthonormal throughoutand the matrix on it is not its own

Three quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 4.23·10⁻⁶ after. The basis's own orthogonality error stays at 9·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 2.5·10⁻¹⁵.

k: 4

The arguments are the ones A condition number for one eigenvalue passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

The projected matrix, against the basis it is supposed to project ontoThree quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 4.23·10⁻⁶ after. The basis's own orthogonality error stays at 9·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 2.5·10⁻¹⁵.1234567810⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³cyclerelative sizea vector kept twice‖T − QᵀAQ‖‖QᵀQ − I‖border recomputedwhich model is wrong‖T − QᵀAQ‖ at cycle 21.1·10⁻¹⁵at cycle 34.2·10⁻⁶‖QᵀQ − I‖, worst9·10⁻¹⁶the basis is orthonormal throughoutand the matrix on it is not its own

Three quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 4.23·10⁻⁶ after. The basis's own orthogonality error stays at 9·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 2.5·10⁻¹⁵.

k: 2

The arguments are the ones Orthogonal is a number passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

The projected matrix, against the basis it is supposed to project ontoThree quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 0.00122 after. The basis's own orthogonality error stays at 7.8·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 4.3·10⁻¹⁵.1234567810⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³cyclerelative sizea vector kept twice‖T − QᵀAQ‖‖QᵀQ − I‖border recomputedwhich model is wrong‖T − QᵀAQ‖ at cycle 28.1·10⁻¹⁶at cycle 30.0012‖QᵀQ − I‖, worst7.8·10⁻¹⁶the basis is orthonormal throughoutand the matrix on it is not its own

Three quantities against the cycle count on a logarithmic vertical axis. The disagreement between the arrowhead and the Rayleigh quotient of its own basis is at the level of rounding for two cycles and reaches 0.00122 after. The basis's own orthogonality error stays at 7.8·10⁻¹⁶ throughout, and the run whose border entries are recomputed stays at 4.3·10⁻¹⁵.

What it checked while drawing

Every figure above asserted its own claims on the way to being drawn, and a claim that failed would have failed the build rather than drawn a wrong picture. Those assertions used to leave no trace at all: a passing one returned true and the only evidence the figure had checked anything was that nothing crashed. The list below is what they actually said, collected by running this generator with an observer installed — not a description of what it is believed to check.

8 distinct claims across 3 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.

a number of retained vectors the method needs

and stops being it after that

and the repaired projection stays the Rayleigh quotient throughout

enough cycles for a second restart to have happened

Jacobi needs a symmetric matrix

matmul shapes agree

on a basis that never loses orthogonality

the arrowhead is the Rayleigh quotient for the first two cycles

Against the rule

The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.

Across the library: the rule bites on 70 of 151 generators — 55 print a residual and 15 are exempt with a published reason; 81 factorise nothing. Read from lib/residual-rule.js, which is the same body the gate enforces from, and the gate's last check fails the build if this page and it disagree about any generator.

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

Eigenvalues, singular values, rank

A condition number for one eigenvalue

In the symmetric case every eigenvalue has condition number exactly one. In this four-by-four matrix two of them have condition number 100.005 and the other two have exactly 1, and the number belongs to the eigenvalue rather than to the matrix.

 Sparsity, and what elimination costs

A threshold between fill and growth

One number decides how small a pivot an elimination will accept. At 0.001 the factor holds 172 entries and the matrix grows by 1,330; at 1 it holds 260 and grows by 1.2. The libraries ship 0.1, and the measurement says why.

 Eigenvalues, singular values, rank

An eigenvalue that arrives twice

A matrix with forty distinct eigenvalues, handed to Lanczos for eighty steps, returns twenty-five extra copies of thirteen of them — the largest arriving five times. Every copy is accurate to 1.9·10⁻⁸ relative. No arithmetic error was made, nothing overflowed, and a caller counting eigenvalues gets the wrong multiplicity from a computation in which no individual number is wrong.

 Eigenvalues, singular values, rank

Keeping the vectors, and losing the bound

Thick restarting keeps the Ritz vectors instead of filtering the starting vector — the same eigenvalues for a third of the products with A. Its residual bound reaches 9.4·10⁻⁴¹ while the residual it bounds sits at 5.7·10⁻⁵, and the eigenvalues are correct to 4.3·10⁻¹⁴ the whole time, so nothing reports it.

 Orthogonality, measured

Orthogonal is a number

"Q is orthogonal" is a claim about a measurable quantity, ‖QᵀQ − I‖, and on the eight-by-eight Hilbert matrix two standard algorithms return 10⁻¹⁵ and 1 for it. The one that returns 1 still reconstructs the matrix perfectly, which is why nothing warns you.

 Eigenvalues, singular values, rank

The gap decides the eigenvector

A symmetric matrix's eigenvalues move by at most the size of the perturbation, whatever the spectrum looks like. Its eigenvectors are governed by a completely different quantity — the distance to the neighbouring eigenvalue — and at a gap of 10⁻⁹ the same perturbation turns them through 27°.

The whole library · All essays · What must fail