Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

breakdown-approach

One function in the breakdown library, called 4 times across 2 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 6 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 arnoldi subdiagonal and the gmres residual against the width of an eigenvalue cluster, n = 30, 5 clusters. A matrix of size 30 whose spectrum is 5 clusters of width η. At η = 0 the Krylov space closes at dimension 5 and the recurrence breaks down there. As η opens up, h_{6,5} rises with a fitted slope of 1.00 and the relative residual at step 5 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 102 between them. The residual at step 4, one short of the breakdown, is 0.0238 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.

breakdown-approach is one function in lib/figures/breakdown.js — breakdown — the zero that is an answer, and the zero that is nothing. 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 Arnoldi subdiagonal and the GMRES residual against the width of an eigenvalue cluster, n = 30, 5 clustersA matrix of size 30 whose spectrum is 5 clusters of width η. At η = 0 the Krylov space closes at dimension 5 and the recurrence breaks down there. As η opens up, h_{6,5} rises with a fitted slope of 1.00 and the relative residual at step 5 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 102 between them. The residual at step 4, one short of the breakdown, is 0.0238 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²cluster width ηmagnitudeh at step 5residual at 5residual at 4fitted over ten decadesslope of h against η1slope of the residual1h ÷ residual, at every stop102residual at step 40.024the zero arrives in proportionand the step before it learns nothing

A matrix of size 30 whose spectrum is 5 clusters of width η. At η = 0 the Krylov space closes at dimension 5 and the recurrence breaks down there. As η opens up, h_{6,5} rises with a fitted slope of 1.00 and the relative residual at step 5 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 102 between them. The residual at step 4, one short of the breakdown, is 0.0238 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.

m: 3

The arguments are the ones Deciding that a zero has arrived 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 Arnoldi subdiagonal and the GMRES residual against the width of an eigenvalue cluster, n = 30, 3 clustersA matrix of size 30 whose spectrum is 3 clusters of width η. At η = 0 the Krylov space closes at dimension 3 and the recurrence breaks down there. As η opens up, h_{4,3} rises with a fitted slope of 1.00 and the relative residual at step 3 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 13.4 between them. The residual at step 2, one short of the breakdown, is 0.1264 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²cluster width ηmagnitudeh at step 3residual at 3residual at 2fitted over ten decadesslope of h against η1slope of the residual1h ÷ residual, at every stop13residual at step 20.13the zero arrives in proportionand the step before it learns nothing

A matrix of size 30 whose spectrum is 3 clusters of width η. At η = 0 the Krylov space closes at dimension 3 and the recurrence breaks down there. As η opens up, h_{4,3} rises with a fitted slope of 1.00 and the relative residual at step 3 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 13.4 between them. The residual at step 2, one short of the breakdown, is 0.1264 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.

m: 5

The arguments are the ones The zero that means it is finished 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 Arnoldi subdiagonal and the GMRES residual against the width of an eigenvalue cluster, n = 30, 5 clustersA matrix of size 30 whose spectrum is 5 clusters of width η. At η = 0 the Krylov space closes at dimension 5 and the recurrence breaks down there. As η opens up, h_{6,5} rises with a fitted slope of 1.00 and the relative residual at step 5 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 102 between them. The residual at step 4, one short of the breakdown, is 0.0238 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²cluster width ηmagnitudeh at step 5residual at 5residual at 4fitted over ten decadesslope of h against η1slope of the residual1h ÷ residual, at every stop102residual at step 40.024the zero arrives in proportionand the step before it learns nothing

A matrix of size 30 whose spectrum is 5 clusters of width η. At η = 0 the Krylov space closes at dimension 5 and the recurrence breaks down there. As η opens up, h_{6,5} rises with a fitted slope of 1.00 and the relative residual at step 5 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 102 between them. The residual at step 4, one short of the breakdown, is 0.0238 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.

m: 2

The arguments are the ones The zero that means it is finished 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 Arnoldi subdiagonal and the GMRES residual against the width of an eigenvalue cluster, n = 30, 2 clustersA matrix of size 30 whose spectrum is 2 clusters of width η. At η = 0 the Krylov space closes at dimension 2 and the recurrence breaks down there. As η opens up, h_{3,2} rises with a fitted slope of 1.00 and the relative residual at step 2 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 4.08 between them. The residual at step 1, one short of the breakdown, is 0.3299 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²cluster width ηmagnitudeh at step 2residual at 2residual at 1fitted over ten decadesslope of h against η1slope of the residual1h ÷ residual, at every stop4.1residual at step 10.33the zero arrives in proportionand the step before it learns nothing

A matrix of size 30 whose spectrum is 2 clusters of width η. At η = 0 the Krylov space closes at dimension 2 and the recurrence breaks down there. As η opens up, h_{3,2} rises with a fitted slope of 1.00 and the relative residual at step 2 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 4.08 between them. The residual at step 1, one short of the breakdown, is 0.3299 and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.

m: 12

The arguments are the ones The zero that means it is finished 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 Arnoldi subdiagonal and the GMRES residual against the width of an eigenvalue cluster, n = 30, 12 clustersA matrix of size 30 whose spectrum is 12 clusters of width η. At η = 0 the Krylov space closes at dimension 12 and the recurrence breaks down there. As η opens up, h_{13,12} rises with a fitted slope of 1.00 and the relative residual at step 12 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 82000 between them. The residual at step 11, one short of the breakdown, is 7.576·10⁻⁵ and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²cluster width ηmagnitudeh at step 12residual at 12residual at 11fitted over ten decadesslope of h against η1slope of the residual1h ÷ residual, at every stop8.2·10⁴residual at step 117.6·10⁻⁵the zero arrives in proportionand the step before it learns nothing

A matrix of size 30 whose spectrum is 12 clusters of width η. At η = 0 the Krylov space closes at dimension 12 and the recurrence breaks down there. As η opens up, h_{13,12} rises with a fitted slope of 1.00 and the relative residual at step 12 with a slope of 1.00 — both exactly proportional to η, at a fixed ratio of 82000 between them. The residual at step 11, one short of the breakdown, is 7.576·10⁻⁵ and stays inside a per cent of that across the whole sweep: the step before the event carries no information about it.

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.

6 distinct claims across 5 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 clusters the recurrence can reach inside the drawn range

an Arnoldi recurrence started from a vector that is not zero

and a matrix large enough that the invariant subspace is a small part of it

and so is the residual at the step it stops on

the subdiagonal is proportional to the cluster width

while the residual one step earlier stays inside a per cent of itself

Against the rule

It draws a decomposition and prints its residual. It calls clusterSweep, and every figure above carries the badge — which residualcheck verifies by looking for it in the emitted SVG rather than by finding the call that builds one. A badge that is constructed and then left out of the body is the failure that check exists for.

Across the library: the rule bites on 113 of 219 generators — 98 print a residual and 15 are exempt with a published reason; 106 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.

Two errors, and whose fault they are

Deciding that a zero has arrived

The previous tolerances were offers — accept this much error, save this much work. A detection threshold is not an offer, because both directions are failures. One matrix here has three genuinely near-invariant subspaces, and the constant somebody typed decides which of them the recurrence stops at; at eight significand bits the same kind of constant produces a proof of something false.

 Iterating, instead of factorising

The zero that means it is finished

Every Krylov method ends by dividing by a number the previous step produced, and when that number is zero the recurrence stops. In Arnoldi the stop is the answer — the subspace has closed, the solution is inside it, and the residual is at the unit roundoff. The literature calls it a lucky breakdown, and the adjective is doing real work.

The whole library · All essays · What must fail