An inner product with no fixed sign

Orthogonal is a number is the essay this collection is built on. Its argument is that orthogonal should stop being an adjective: measure ‖QᵀQ − I‖, print it beside the figure, and two algorithms that are the same algebra written in a different order stop being equally good and start returning 10⁻¹⁵ and 1.

The measurement is an inner product of two columns whose true value is zero — which the vector that hides it puts at κ = 7.4·10¹⁵, the worst end of the census. So the obvious question, asked of the site’s own instrument: what does it do when the reduction computing it is divided differently?

Five distinct values, on both sides of zero, and several of them exactly zero — a computed quantity whose sign is decided by how many workers were available. Across the whole factor, 125 of the 1,128 off-diagonal pairs — one in nine — have a sign that is not a property of the matrix.

And the norm is fine #

Here is the other half, and it is the field’s one genuinely reassuring result.

‖QᵀQ − I‖_F over the same ten partitionings moves by a factor of 1.0243. Two and a half per cent, and between 1.015 and 1.030 across the whole sweep of conditionings. Every figure on this site that prints an orthogonality residual is printing a number whose leading digit and whose order of magnitude are properties of the factorisation rather than of the machine.

The reason is aggregation. The norm is a square root of a sum of 2,304 squared entries, each of which the partitioning perturbs independently and in an unpredictable direction. Independent perturbations of many quantities do not accumulate in a norm; they average, and a norm of n² quantities each moved by a relative O(1) moves by a relative O(1/n).

That is the same √n the mechanism essay derives for a reduction’s own error, appearing one level up: where the disagreement comes from shows that a reduction’s roundings average rather than accumulate, and here the entries average rather than accumulate. Both are the same statement about many small independent quantities.

Why an aggregate is not always safe #

The rule the previous section is about to state has an exception, and stating it here keeps the rule honest.

A norm averages the disagreements of its entries when the entries are independent and the norm is a sum of their squares. Both clauses matter.

A maximum is not an average. ‖QᵀQ − I‖_∞ takes the largest row sum, which is dominated by a handful of entries rather than by all of them, and inherits their instability in proportion. The site’s own figures use the Frobenius norm nearly everywhere, which is fortunate rather than deliberate.

And the independence fails where the entries share terms. Every entry of QᵀQ is built from the same Q, so a change of partitioning that moves one column’s roundings moves every entry involving that column together. What saves the norm here is that a partitioning perturbs each inner product separately — the reduction is per entry — rather than perturbing the matrix Q itself.

Change that and the conclusion changes. If the partitioning had moved the factorisation instead of the check — if Q itself had been computed differently — the perturbations of the entries would be correlated, the averaging argument would fail, and the norm would move by more. That is the situation a genuinely parallel QR is in, and it is why a reduction that changes the order measures a different ‖QᵀQ − I‖ for a tree factorisation than for a sweep — 1.65·10⁻¹⁵ against 9.95·10⁻¹⁵, a factor of six, from two algorithms rather than from two partitionings of one.

So: an aggregate of independently perturbed quantities is stable, an aggregate of jointly perturbed ones is not, and the difference is whether the machine changed the reduction or the algorithm.

The rule this yields #

The two halves together give the field’s sharpest practical rule, and it is short enough to be remembered:

Report the norm. Never read one entry.

An aggregate over many independently rounded quantities is stable to a few per cent. A single one of them is not stable at all, and if it is near zero it is not stable in sign.

That rule has consequences beyond orthogonality checks, because a great deal of numerical software reads exactly one entry:

A componentwise backward error asks which equation is worst satisfied, which is a maximum over entries rather than a norm of them — accurate is not a property of a method makes the case that componentwise measurements are the sharper ones, and they are. They are also the ones whose answer moves.

A pivot search takes a maximum over a column, which is a comparison between entries, and two entries that differ by less than their own disagreement can swap order.

A convergence test on the largest residual component rather than on the residual norm is the same thing again.

And a check for exact orthogonality — is qᵢᵀqⱼ zero — is a sign test on the quantity in the hero figure, which is the case with no room at all.

What the figure is showing, exactly #

Worth spelling out, because the vertical axis is in units of the rounding and that is easy to misread as a normalisation trick.

The two columns are orthonormal to the accuracy a Householder factorisation delivers, which is 1.8·10⁻¹⁵ in the norm and about 10⁻¹⁷ per entry at this size. Their exact inner product — the sum of the 48 products, computed by an expansion that does not round — is not zero either: the columns are orthogonal in exact arithmetic only if Q is, and the computed Q is orthogonal to the rounding level.

So there are three quantities in play and only two of them are on the figure. The true inner product of the columns as stored, which the expansion gives; the computed value at each partitioning, which is what is drawn; and zero, which is what the algebra says and neither of the first two is.

The figure’s line at zero is the algebra’s value. The dots are ten answers to a question whose correct answer is 2.8·10⁻¹⁷ of one thing or another, and the disagreement between them is the same size as the answer.

Where the zeros come from #

Three of the ten values in the hero figure are exactly zero, which looks like an artefact and is the clearest evidence in the field that the picture is arithmetic rather than noise.

An inner product of two orthonormal columns is a sum of 48 products, each about 1/48 in magnitude, whose exact total is zero to within the rounding of the vectors themselves. The computed value is therefore a sum of roundings, and roundings are multiples of the spacing at the scale they were committed — here 2⁻⁵⁴ or thereabouts. So the computed value is a small multiple of 1.39·10⁻¹⁷ — half the largest value in the figure — and the ten partitionings return −1.75, +2, +1, −2, 0, 0, +1, 0, 0 and 0 of them.

Zero is not a special outcome; it is one of the four or five values available, and it occurs when the roundings happen to cancel. What it means for a caller is worse than a nonzero answer would be: a test asking are these columns exactly orthogonal returns yes on three machines of ten and no on the other seven, and the seven disagree about the direction of the failure.

This is the same quantisation the numbers below the smallest one meets at the other end of the range, where the representable numbers are a lattice rather than a continuum. Near zero every computed quantity is a lattice, and a comparison with zero is a question about which lattice point a set of roundings landed on.

What the sweep does not show #

The drag runs the conditioning of the matrix from 10² to 10¹², and the picture barely changes: the entries stay at the rounding level and about a ninth of them keep no sign at every stop.

That is a fact about the factorisation rather than about this field. A Householder QR’s loss of orthogonality is flat in κ — 1.8·10⁻¹⁵ across eleven decades, which is the measurement orthogonal is a number is built on and the reason the method is recommended. So there is nothing for the conditioning to degrade: the entries were always at the rounding level and the rounding level is where the partitioning has its say.

Run the same measurement on classical Gram–Schmidt and the picture is different in an instructive way. Its ‖QᵀQ − I‖ on this matrix is 1.179, and it is 1.179 at every partitioning to four figures — because the loss of orthogonality there is a real quantity, produced by the algorithm and enormous compared with any rounding, so a change of reduction cannot move it. The disagreement is visible only where the quantity is small.

That is worth stating as its own observation. A badly behaved computation returns a stable wrong answer; a well behaved one returns an answer whose last digits belong to the machine. Reproducibility and quality are, once again, not the same axis — and here they point in opposite directions.

How many entries, and why one in nine #

The count — 125 of 1,128 — deserves a sentence, because it is neither one nor all and both of those would be easier to explain.

An off-diagonal entry of QᵀQ has a true value at the rounding level and a computed value that is a few multiples of the local spacing. Whether two partitionings put it on opposite sides of zero depends on whether its typical magnitude is comparable with the disagreement between them: an entry that comes out at eight multiples of the spacing has room to move by two without changing sign, and one that comes out at one multiple does not.

So the fraction with no fixed sign is the fraction whose computed value is within the run-to-run disagreement of zero, which for a distribution of entries spread over a few multiples of the spacing is a fraction of order one in ten. Measured across the drag’s six conditionings it stays between 8.3% and 11.1% — 94, 95, 110, 112, 120 and 125 pairs of 1,128 — while the matrix being factorised changes by ten orders of magnitude in its condition number. That stability is what makes it a statement about the arithmetic rather than about this matrix.

The number to carry is not 125. It is that about a tenth of the entries of a computed orthogonality residual have no determined sign, on any matrix, at any conditioning, in this precision.

What this does to the site’s own figures #

The honest accounting, since this collection prints orthogonality residuals on dozens of pages.

The values drawn are stable, because the builds are serial. Every figure here is computed in one process, in one order, from a seeded stream, and the build’s own check that a rebuild reproduces the deployed content hash would fail if any of them moved. The site is in the corner of accuracy and agreement are different properties’s table where the order never changes, so the question never arises.

A reader reproducing them in a threaded environment should expect the norms to agree — they are aggregates, stable to a few per cent — and should not expect an entry to agree at all. Where a figure draws the matrix QᵀQ entry by entry, as orthogonal is a number’s companion does, the individual numbers shown are one machine’s.

And the claims are unaffected, because every claim on this site is about an order of magnitude or a ratio: classical Gram–Schmidt loses orthogonality like κ² and modified like κ, Householder is flat at 10⁻¹⁵. Those are statements about slopes across decades, and a 2.4% wobble at each point does not touch them.

That last paragraph is the general answer to does this invalidate anything. It does not, and the reason is worth carrying: a claim stated as an order of magnitude survives the machine, and a claim stated to three digits does not. This site’s habit of quoting a fitted exponent — 1.95 for the squaring, 0.93 after a second pass — is a habit that happens to be robust to the field it did not know about.

The instrument that measures the instrument #

There is something slightly recursive about this essay and it is worth naming rather than leaving as a discomfort.

This collection’s method is to measure rather than assert: an adjective becomes a number, the number is printed on the figure, and a gate refuses a figure that draws a factorisation without one. The essay above takes that instrument and measures it, and finds that its aggregate is trustworthy to two and a half per cent and its parts are not trustworthy at all.

Two responses are available and only one of them is right.

The wrong one is to conclude that measurement is undermined. It is not: the norm is stable, the claims are about slopes across decades, and the whole apparatus does what it was built to do. A measurement with a known 2.4% variability is a measurement, and knowing the figure is better than assuming it is zero.

The right one is that an instrument needs its own error bar, and this collection has been printing residuals without one for nineteen fields. Not because anybody was careless — the variation is invisible on a serial build, which is what every figure here is — but because the question was never asked. Printing κ of the inner product beside ‖QᵀQ − I‖ would be the honest form, and it costs one pass.

That is the same move the site made when it stopped saying orthogonal and started printing a number. The number needs a number.

The one measurement that would be worth adding #

If the site were to print one more number beside its orthogonality residuals, it would not be a reproducibility figure. It would be κ of the inner product — Σ|qᵢₖqⱼₖ| divided by the computed value — which is one pass, says how much of the printed number is rounding, and would have made this whole essay a footnote rather than a discovery.

At κ = 10¹⁶ the number printed is entirely rounding and its digits mean nothing; at κ = 10² it is a measurement. Both appear in this collection, and nothing on the page distinguishes them.

One line #

The site’s signature measurement survives a change of machine because it is a norm of two thousand independently rounded quantities; the quantities themselves do not, and one in nine of them has no determined sign.

At other settings #