Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

barrier-error

One function in the barrier library, called 19 times across 9 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 11 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 both forms of an interior-point step: two condition numbers that climb together and two errors that do not. One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 3 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 29.04 to 3.044·10¹⁵ for the augmented form and 155.8 to 2.403·10¹⁶ for the condensed one, within a factor of 7.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.3098 and the augmented form's stays at 1.035·10⁻¹⁵ — fifteen correct digits at a condition number of 3.04·10¹⁵.

barrier-error is one function in lib/figures/barrier.js — the barrier — a condition number sent to infinity on purpose, and the number that describes the error. 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.

Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 3 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 29.04 to 3.044·10¹⁵ for the augmented form and 155.8 to 2.403·10¹⁶ for the condensed one, within a factor of 7.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.3098 and the augmented form's stays at 1.035·10⁻¹⁵ — fifteen correct digits at a condition number of 3.04·10¹⁵.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴3·10¹⁵its relative error10⁻¹⁵κ₂ condensed2.4·10¹⁶its relative error0.31the same step, written two waysand only one of them is solvable

One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 3 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 29.04 to 3.044·10¹⁵ for the augmented form and 155.8 to 2.403·10¹⁶ for the condensed one, within a factor of 7.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.3098 and the augmented form's stays at 1.035·10⁻¹⁵ — fifteen correct digits at a condition number of 3.04·10¹⁵.

active: 3

The arguments are the ones A condition number sent to infinity 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.

Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 3 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 29.04 to 3.044·10¹⁵ for the augmented form and 155.8 to 2.403·10¹⁶ for the condensed one, within a factor of 7.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.3098 and the augmented form's stays at 1.035·10⁻¹⁵ — fifteen correct digits at a condition number of 3.04·10¹⁵.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴3·10¹⁵its relative error10⁻¹⁵κ₂ condensed2.4·10¹⁶its relative error0.31the same step, written two waysand only one of them is solvable

One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 3 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 29.04 to 3.044·10¹⁵ for the augmented form and 155.8 to 2.403·10¹⁶ for the condensed one, within a factor of 7.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.3098 and the augmented form's stays at 1.035·10⁻¹⁵ — fifteen correct digits at a condition number of 3.04·10¹⁵.

active: 4

The arguments are the ones A condition number sent to infinity 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.

Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 4 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 31.22 to 2.193·10¹⁵ for the augmented form and 102.3 to 2.794·10¹⁶ for the condensed one, within a factor of 12.7 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.06652 and the augmented form's stays at 3.49·10⁻¹⁵ — fifteen correct digits at a condition number of 2.19·10¹⁵.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴2.2·10¹⁵its relative error3.5·10⁻¹⁵κ₂ condensed2.8·10¹⁶its relative error0.067the same step, written two waysand only one of them is solvable

One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 4 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 31.22 to 2.193·10¹⁵ for the augmented form and 102.3 to 2.794·10¹⁶ for the condensed one, within a factor of 12.7 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.06652 and the augmented form's stays at 3.49·10⁻¹⁵ — fifteen correct digits at a condition number of 2.19·10¹⁵.

active: 1

The arguments are the ones A condition number sent to infinity 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.

Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 1 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 28.23 to 1.439·10¹⁶ for the augmented form and 162.7 to 4.182·10¹⁷ for the condensed one, within a factor of 29.1 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 1 and the augmented form's stays at 1.352·10⁻¹⁵ — fifteen correct digits at a condition number of 1.44·10¹⁶.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴1.4·10¹⁶its relative error1.4·10⁻¹⁵κ₂ condensed4.2·10¹⁷its relative error1the same step, written two waysand only one of them is solvable

One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 1 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 28.23 to 1.439·10¹⁶ for the augmented form and 162.7 to 4.182·10¹⁷ for the condensed one, within a factor of 29.1 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 1 and the augmented form's stays at 1.352·10⁻¹⁵ — fifteen correct digits at a condition number of 1.44·10¹⁶.

active: 2

The arguments are the ones A condition number sent to infinity 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.

Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 2 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 28.34 to 1.401·10¹⁶ for the augmented form and 160.6 to 1.673·10¹⁷ for the condensed one, within a factor of 11.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 1 and the augmented form's stays at 5.024·10⁻¹⁵ — fifteen correct digits at a condition number of 1.4·10¹⁶.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴1.4·10¹⁶its relative error5·10⁻¹⁵κ₂ condensed1.7·10¹⁷its relative error1the same step, written two waysand only one of them is solvable

One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 2 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 28.34 to 1.401·10¹⁶ for the augmented form and 160.6 to 1.673·10¹⁷ for the condensed one, within a factor of 11.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 1 and the augmented form's stays at 5.024·10⁻¹⁵ — fifteen correct digits at a condition number of 1.4·10¹⁶.

active: 5

The arguments are the ones A condition number sent to infinity 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.

Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 5 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 31.53 to 2.161·10¹⁵ for the augmented form and 97.8 to 1.482·10¹⁶ for the condensed one, within a factor of 6.86 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.2882 and the augmented form's stays at 4.805·10⁻¹⁵ — fifteen correct digits at a condition number of 2.16·10¹⁵.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴2.2·10¹⁵its relative error4.8·10⁻¹⁵κ₂ condensed1.5·10¹⁶its relative error0.29the same step, written two waysand only one of them is solvable

One Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 5 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 31.53 to 2.161·10¹⁵ for the augmented form and 97.8 to 1.482·10¹⁶ for the condensed one, within a factor of 6.86 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.2882 and the augmented form's stays at 4.805·10⁻¹⁵ — fifteen correct digits at a condition number of 2.16·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.

11 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.

a factorisation that did not break down

a finite double, since an infinity is not a rational

a pivot rule this routine implements

a problem with constraints and unknowns

a size the exact rational solve can afford at every μ

an active set that is neither empty nor everything

and its error does not move

LU is for square matrices

matmul shapes agree

the augmented condition number reaches 10¹⁴

while the condensed one loses every digit

Against the rule

It draws a decomposition and prints its residual. It calls barrierSweep, 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 165 of 306 generators — 150 print a residual and 15 are exempt with a published reason; 141 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.

The matrix a constraint makes

A condition number sent to infinity

An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.

 Eigenvalues, singular values, rank

An eigenvalue count that cannot be slightly wrong

Every spectral computation on this site returns floats with errors in them. Counting eigenvalues below a shift by the signs of an unpivoted elimination returns an integer, and an integer cannot be 6.9999999997 — so the answer is exactly right, or wrong by a whole eigenvalue, and where the second happens is a band of measurable width.

 Orthogonality, measured

The basis nobody chose on purpose

A method that eliminates a constraint has to pick a basis for its null space, and every basis is correct. Their condition numbers are eight orders apart, the reduced problem inherits the square, and the choice is usually made by a one-line rule nobody thought of as a numerical decision.

 Randomised, and the guarantee that changes kind

The half of a problem a sketch may touch

A sketch guarantees that a norm is preserved to within a factor. An equality constraint is a statement that a quantity is zero, and no multiplicative guarantee says anything about zero. Sketch a constrained problem written as a weighted one and the constraint is not destroyed — it is demoted, from a violation of 1/τ² to one of ε/τ, exactly half the exponent.

 The matrix a constraint makes

The regularisation that legalises every order

Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.

 The matrix a constraint makes

The zero that is not a missing entry

A constrained minimisation produces a matrix with a zero block, and the zero is a theorem rather than a sparsity pattern. No pivot order makes it positive definite, no precision changes that, and Cholesky does not fail somewhere on it — it fails at the first constraint row, on a number the problem already contained.

 Two errors, and whose fault they are

Two condition numbers of one matrix

κ₂ is a worst case over perturbations of a given norm, and a normwise perturbation may put its whole budget on the smallest entry. The componentwise number is a worst case over perturbations proportional to the entries, which is what a backward-stable factorisation actually makes. On one matrix they are 3·10¹³ and 13.3, and the error obeys the second.

 The matrix a constraint makes

Two ways to remove a constraint

A constrained system can be reduced by eliminating the multipliers or by eliminating the constrained directions. Both give the same answer in exact arithmetic and inherit different condition numbers — one of them squares the constraint's, and the other does not contain it at all.

 When the problem arrives again

What survives one step of the barrier

An interior-point method solves the same system dozens of times with the same pattern and different numbers, and exactly p entries change between one step and the next. The pattern is reusable for ever. The factorisation is reusable for none of them, and the threshold that says so is a reduction factor of about a per cent against schedules that use ten.

The whole library · All essays · What must fail