Loss of orthogonality against condition number, in binary64
At its defaults it draws loss of orthogonality against condition number, in binary64. A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
orth-loss-curve is one function in lib/figures/ortho.js —
orthogonality — ‖qᵀq − i‖ as a measurement rather than an adjective. 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.
A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
bits: 53
The arguments are the ones A reflection cannot stop being one passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
bits: 20
The arguments are the ones A reflection cannot stop being one passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
bits: 32
The arguments are the ones A reflection cannot stop being one passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
bits: 38
The arguments are the ones A reflection cannot stop being one passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
bits: 44
The arguments are the ones A reflection cannot stop being one passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.
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.
125 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 both still reconstruct A at κ = 10 — checked 3 times
classical is never much better than modified at κ = 10 — checked 3 times
Householder holds orthogonality at κ = 10 — checked 3 times
a block of sixteen carries a triangle of 136 numbers
a block size that divides the column count
a block size that tiles sixteen columns into more than one block
a block size the dial draws
a block size the sweep uses
a finite double, since an infinity is not a rational
a handful of seeds, each costing an exact solve per κ
a mode this family draws: lsq, padded, block, reflector or wy
a one per cent perturbation of the direction leaves the factorisation orthogonal
a perturbation of the triangle large enough to see and small enough to be an error
a placement of the ill-conditioning the block construction offers
a placement of the ill-conditioning the construction offers
a placement of the ill-conditioning this file builds
a Q orthogonal to rounding can give an answer three orders further from Householder's than one that is not
a reflector storage form this routine implements
a residual between zero and a hundredth of ‖b‖ — larger and the least-squares solution itself moves with κ
a tall matrix the sweep can afford at every κ and seed
a tall problem the exact rational solve can afford
a within-block QR this file implements
a κ the block sweep draws
across blocks, the classical order of removal loses orders the modified one keeps
an exact normal-equations matrix that is nonsingular
and both still reconstruct A at κ = 10¹⁰
and both still reconstruct A at κ = 10¹¹
and both still reconstruct A at κ = 10⁴
and both still reconstruct A at κ = 10⁵
and both still reconstruct A at κ = 10⁶
and both still reconstruct A at κ = 10⁷
and both still reconstruct A at κ = 10⁸
and both still reconstruct A at κ = 10⁹
and forming Qᵀb costs modified Gram–Schmidt three orders or more somewhere past κ = 10⁶
and Householder ends the range below both of them
and is orthogonal to rounding all the same
and the padded Q's top block is the size of the lost orthogonality at κ = 100
and the padded Q's top block is the size of the lost orthogonality at κ = 10¹⁰
and the padded Q's top block is the size of the lost orthogonality at κ = 10¹²
and the padded Q's top block is the size of the lost orthogonality at κ = 10¹⁴
and the padded Q's top block is the size of the lost orthogonality at κ = 10⁴
and the padded Q's top block is the size of the lost orthogonality at κ = 10⁶
and the padded Q's top block is the size of the lost orthogonality at κ = 10⁸
and the same perturbation of the scalar does not
block CGS gains nothing from the appended block, across
block CGS gains nothing from the appended block, inside
block CGS gains nothing from the appended block, mixed
blocks that tile the columns and hold more than one
Cholesky QR inside blocks that are themselves well conditioned does not stop
classical is never much better than modified at κ = 10¹⁰
classical is never much better than modified at κ = 10¹¹
classical is never much better than modified at κ = 10⁴
classical is never much better than modified at κ = 10⁵
classical is never much better than modified at κ = 10⁶
classical is never much better than modified at κ = 10⁷
classical is never much better than modified at κ = 10⁸
classical is never much better than modified at κ = 10⁹
classical loses orthogonality by orders of magnitude that modified does not
classical twice with Householder inside holds rounding level at κ = 100
classical twice with Householder inside holds rounding level at κ = 10¹⁰
classical twice with Householder inside holds rounding level at κ = 10¹²
classical twice with Householder inside holds rounding level at κ = 10¹⁴
classical twice with Householder inside holds rounding level at κ = 10⁴
classical twice with Householder inside holds rounding level at κ = 10⁶
classical twice with Householder inside holds rounding level at κ = 10⁸
enough of the κ range with a solution that stays put
Householder holds orthogonality at κ = 10¹⁰
Householder holds orthogonality at κ = 10¹¹
Householder holds orthogonality at κ = 10⁴
Householder holds orthogonality at κ = 10⁵
Householder holds orthogonality at κ = 10⁶
Householder holds orthogonality at κ = 10⁷
Householder holds orthogonality at κ = 10⁸
Householder holds orthogonality at κ = 10⁹
matmul shapes agree
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 100
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 10¹⁰
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 10¹²
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 10¹⁴
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 10⁴
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 10⁶
modified Gram–Schmidt on [A b] is within ten times Householder at κ = 10⁸
the R factors agree to rounding at κ = 100
the R factors agree to rounding at κ = 10¹⁰
the R factors agree to rounding at κ = 10¹²
the R factors agree to rounding at κ = 10¹⁴
the R factors agree to rounding at κ = 10⁴
the R factors agree to rounding at κ = 10⁶
the R factors agree to rounding at κ = 10⁸
the two classical routes are the same arithmetic at κ = 100
the two classical routes are the same arithmetic at κ = 10¹⁰
the two classical routes are the same arithmetic at κ = 10¹²
the two classical routes are the same arithmetic at κ = 10¹⁴
the two classical routes are the same arithmetic at κ = 10⁴
the two classical routes are the same arithmetic at κ = 10⁶
the two classical routes are the same arithmetic at κ = 10⁸
while a relative perturbation of that triangle is not free
while the direction's perturbation does move the factorisation
while the padded Q is orthogonal at κ = 100
while the padded Q is orthogonal at κ = 10¹⁰
while the padded Q is orthogonal at κ = 10¹²
while the padded Q is orthogonal at κ = 10¹⁴
while the padded Q is orthogonal at κ = 10⁴
while the padded Q is orthogonal at κ = 10⁶
while the padded Q is orthogonal at κ = 10⁸
with nothing between the blocks, classical and modified removal are the same at κ = 100
with nothing between the blocks, classical and modified removal are the same at κ = 10¹⁰
with nothing between the blocks, classical and modified removal are the same at κ = 10¹²
with nothing between the blocks, classical and modified removal are the same at κ = 10¹⁴
with nothing between the blocks, classical and modified removal are the same at κ = 10⁴
with nothing between the blocks, classical and modified removal are the same at κ = 10⁶
with nothing between the blocks, classical and modified removal are the same at κ = 10⁸
with two blocks there is one projection, so classical and modified coincide at κ = 100
with two blocks there is one projection, so classical and modified coincide at κ = 10¹⁰
with two blocks there is one projection, so classical and modified coincide at κ = 10¹²
with two blocks there is one projection, so classical and modified coincide at κ = 10¹⁴
with two blocks there is one projection, so classical and modified coincide at κ = 10⁴
with two blocks there is one projection, so classical and modified coincide at κ = 10⁶
with two blocks there is one projection, so classical and modified coincide at κ = 10⁸
Against the rule
It calls a factoriser without drawing a factorisation
(qrHouseholder, gramSchmidt),
so the rule is written down as not applying, with the reason:
the whole plot is ‖QᵀQ − I‖ — the residual is the vertical axis
The exemption list is the interesting half of the rule rather than an escape hatch — it is
where a decision about a figure had to be argued in one line. residualcheck
refuses an exemption that is not doing work, and rejected ten of the fifteen written for the
expansion's figures on exactly that ground: a figure whose vertical axis is a residual
satisfies the rule by construction, and touching a factoriser does not by itself require an
entry.
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.
A reflection cannot stop being one
Householder QR holds orthogonality at 10⁻¹⁵ whatever the condition number of the matrix, and Gram–Schmidt does not. The reason is not that it is more careful. It is that its Q is built from unit vectors, and rounding a unit vector gives a different reflection rather than a broken one.
Orthogonality, measuredA stable block is not a stable basis
Block Gram–Schmidt orthogonalises twice over — between blocks, and inside each one. Householder inside the blocks does not stop the classical between-block step losing orthogonality like κ², 4.2·10⁻³ at κ = 4.3·10⁷, and a second pass does not stop Cholesky QR inside the blocks breaking down at κ = 10⁸. Each level fails only on ill-conditioning placed at its own level, and one variant holds 3·10⁻¹⁵ on every placement.
Orthogonality, measuredA triangle where the scalar was
Every level-3 QR assembles a block of reflectors into Q = I − Y T Yᵀ, and T is computed by a recurrence whose inputs are its own previous columns. A block of sixteen carries 136 computed numbers where sixteen separate reflections carry sixteen. The orthogonality it produces is 3.9·10⁻¹⁵ against the single reflector's 7.8·10⁻¹⁶ — a factor of five for a hundred and thirty-six times as many things that have to be right.
Orthogonality, measuredEight blocks and sixty-four reflections
One block of sixteen reflectors, assembled as I − Y T Yᵀ, departed from orthogonality five times as far as a single reflection, and the question was whether a factorisation of many blocks multiplies that factor. It does not. On 96 × 64 matrices eight blocks of eight end at 1.42·10⁻¹⁴ — within a fifth of the root-sum-square of their own departures, and less than half their sum — while the same factorisation taken one reflector at a time ends at 2.91·10⁻¹⁴. A block departs more than a reflector, and there are an eighth as many of them. And a nearly dependent column that swells the triangle's entries to 10²⁶ costs the product nothing.
Orthogonality, measuredOne number that has to be right
Householder's orthogonality was called structural: a reflection is built from a unit vector, so rounding the vector names a different reflection rather than a broken one. Tested by breaking it, the claim is narrower and sharper. Perturb every component of the reflector by a relative 10⁻², and ‖QᵀQ − I‖ stays at 1.5·10⁻¹⁵ while the factorisation moves to 5·10⁻³. Perturb the one stored scalar by the same amount and ‖QᵀQ − I‖ is 6.5·10⁻². The structure is one degree of freedom, and the departure is four times its relative error.
Orthogonality, measuredOrthogonal 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.
Orthogonality, measuredThe factor nobody forms
A blocked Householder factorisation's orthogonal factor, multiplied out, departs from orthogonality half as far in blocks of sixteen as one reflector at a time, and that was read as blocking buying a factor of two. Libraries do not multiply it out. Applied to vectors through its stored blocks — which is how every caller uses it — the same factor departs by 3.1 to 4.0·10⁻¹⁵ at every block size from one to sixty-four, and stops growing after about twenty reflectors instead of adding them up. The factor of two was the price of forming the product, and a factor that is never formed never pays it.
Orthogonality, measuredThe residual the appended block cannot remove
Appending b as one more block made block modified Gram–Schmidt solve least squares as well as Householder, ten million times better than the same Q through Qᵀb at κ = 10⁸ — on problems with no residual. Give b a component outside the range and every stable route's error rises with it, while Qᵀb's, already at κ²u, does not move. The appended block's advantage then falls as one over the residual: 5,400 at a relative residual of 10⁻⁴, 54 at a per cent, none at one. It never falls behind Householder by more than a factor of four. What the residual decides is whether the extra block is worth its synchronisations, and the answer is yes up to a residual of about a per cent.
Orthogonality, measuredThe right-hand side as one more column
Modified Gram–Schmidt's Q is 4.3·10⁻⁹ from orthogonal at κ = 10⁸, and a least-squares solve that multiplies b by it is wrong by 0.13. Hand the same routine b as an extra column instead and the answer is right to 2.7·10⁻¹⁰ — closer than Householder's 4.0·10⁻⁹. Classical Gram–Schmidt gains nothing from the same trick, to the last bit.
Orthogonality, measuredTwo Gram–Schmidts
One argument changes. Classical Gram–Schmidt projects the original column onto each previous direction; modified projects what is left of it. In exact arithmetic the coefficients are identical. In floating point they differ by eight orders of magnitude in the thing that matters.
Orthogonality, measuredWhat the appended block inherits
Modified Gram–Schmidt on [A b] solves least squares as well as Householder, although its Q is not orthogonal. A block code appends b as one more block. Block modified Gram–Schmidt inherits the rescue at every placement of the ill-conditioning: at κ = 10⁸ the appended block gives 6.9·10⁻¹⁰ where the same Q through Qᵀb gives 8.9·10⁻³. Block classical Gram–Schmidt gets the same wrong answer both ways, to the last bit. And the variant whose Q is orthogonal to 10⁻¹⁵ — two passes with Cholesky QR inside — is a hundred thousand times worse than Householder when the ill-conditioning is inside the blocks, because its R is wrong.