Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

The worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 8

One function in the relacc library, called 7 times across 2 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 44 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 worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 8. Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.1 decades — 3.63·10⁻¹⁴ — and by 11 decades it is at 14.5, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

grading-sweep is one function in lib/figures/relacc.js — relative accuracy — small compared to what, against an exact rational answer. 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 worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 8Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.1 decades — 3.63·10⁻¹⁴ — and by 11 decades it is at 14.5, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.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

Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.1 decades — 3.63·10⁻¹⁴ — and by 11 decades it is at 14.5, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

n: 8

The arguments are the ones A threshold the matrix does not set passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

The worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 8Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.1 decades — 3.63·10⁻¹⁴ — and by 11 decades it is at 14.5, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.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

Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.1 decades — 3.63·10⁻¹⁴ — and by 11 decades it is at 14.5, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

n: 4

The arguments are the ones A threshold the matrix does not set passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

The worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 4Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 1.8 decades — 4.69·10⁻¹⁵ — and by 10 decades it is at 1, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.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 grading4.7·10⁻¹⁵and at the widest1Jacobi, worst over the sweep7.1·10⁻¹⁶zero shift, worst6·10⁻¹⁶the definition is not a methodand squaring buries what it squares

Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 1.8 decades — 4.69·10⁻¹⁵ — and by 10 decades it is at 1, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

n: 12

The arguments are the ones A threshold the matrix does not set passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

The worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 12Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 3.3 decades — 9.14·10⁻¹³ — and by 10 decades it is at 2.02, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.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 grading9.1·10⁻¹³and at the widest1Jacobi, worst over the sweep1.5·10⁻¹⁵zero shift, worst1.8·10⁻¹⁵the definition is not a methodand squaring buries what it squares

Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 3.3 decades — 9.14·10⁻¹³ — and by 10 decades it is at 2.02, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

n: 6

The arguments are the ones A threshold the matrix does not set passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

The worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 6Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 1.5 decades — 6.79·10⁻¹⁵ — and by 11 decades it is at 55.4, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.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 grading6.8·10⁻¹⁵and at the widest1Jacobi, worst over the sweep1.1·10⁻¹⁵zero shift, worst10⁻¹⁵the definition is not a methodand squaring buries what it squares

Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 1.5 decades — 6.79·10⁻¹⁵ — and by 11 decades it is at 55.4, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

n: 10

The arguments are the ones A threshold the matrix does not set passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

The worst relative error over the whole spectrum, against how many decades the matrix is graded over, n = 10Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.7 decades — 1.81·10⁻¹³ — and by 11 decades it is at 1, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.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 grading1.8·10⁻¹³and at the widest3·10⁵Jacobi, worst over the sweep1.9·10⁻¹⁵zero shift, worst1.1·10⁻¹⁵the definition is not a methodand squaring buries what it squares

Each point is one bidiagonal matrix and the worst relative error any of its singular values suffers, measured against a Sturm bisection in exact rationals. The route through BᵀB is as good as anything at 2.7 decades — 1.81·10⁻¹³ — and by 11 decades it is at 1, which is not an error in the answer, it is the answer. One-sided Jacobi and the zero-shift bidiagonal sweep are flat at about the unit roundoff across the whole range, which is the claim this site's own SVD has been making in a source comment since it was written and had never measured.

What it checked while drawing

Every figure above checked its own claims on the way to being drawn, and a claim that failed would have stopped the picture rather than shipped a wrong one. Those checks 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.

44 distinct claims across 6 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.

and the zero shift holds at 2 decades — checked 18 times

Jacobi holds at 2 decades — checked 18 times

a finite number to convert exactly

a grading of at least one bit per row, so the matrix is actually graded

a size the exact bisection can afford at every grading

a value that is a dyadic rational, which every float is

and at a wide one it is not

Jacobi needs a symmetric matrix

matmul shapes agree

while at a narrow grading BᵀB is as good as anything

Against the rule

It draws a decomposition and prints its residual. It calls gradingSweep, 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 217 of 397 generators — 199 print a residual and 18 are exempt with a published reason; 180 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 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.

 Eigenvalues, singular values, rank

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.

The whole library · All essays · What must fail