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.

Both columns are flat across ten orders of conditioning. At κ = 10², 10⁴, 10⁶ and 10¹⁰ the pairs that flip number 112, 110, 95 and 120 of 1,128 — 8.4% to 10.6%, with no trend — and the norm moves by 1.0181, 1.0157, 1.0301 and 1.0232 times, all within 3%.

Neither the aggregate nor the entries know what matrix they came from, which is the whole of the argument. A reader might expect a badly conditioned factorisation to produce both a worse norm and more sign confusion, and it produces neither: the norm moves by two per cent at κ = 10² and by two per cent at κ = 10¹⁰, and about a tenth of the entries have no fixed sign at both. The conditioning decides how large the residual is; it does not decide how reproducible either the residual or its entries are, and those are separate properties that a single printed number conflates.

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 #

The obvious candidate is κ of the inner product — Σ|qᵢₖqⱼₖ| divided by the computed value — which is one pass and says how much of the printed number is rounding. At κ = 10¹⁶ the number printed is entirely rounding and its digits mean nothing; at κ = 10² it is a measurement.

That reasoning is right and the application is not, which is worth working out rather than recommending. Gram–Schmidt on a 12×12 matrix at four condition numbers, both variants, taking the off-diagonal pair with the worst summation condition:

Σ|terms| never leaves the range 0.63 to 0.82, and it cannot. The columns are unit vectors, so Σ|qᵢₖqⱼₖ| ≤ ‖qᵢ‖‖qⱼ‖ = 1 by Cauchy–Schwarz, and for a random pair it sits near 2/π. The numerator of the proposed diagnostic is pinned by the normalisation.

So κ is 0.7 divided by the answer — the residual again, inverted. On precisely the figures it was proposed for it carries nothing the printed number does not already carry, and the verdict it prints is the same verdict every time: zero to two real digits, at every condition number and both variants, with the top row’s value exactly zero and its κ therefore infinite.

There is a second reading in the same table that is worth more than the first. Wherever the two variants’ residuals actually differ, the one with the better residual has the worse conditioning — modified Gram–Schmidt at 10¹⁶ to 10¹⁸ against classical at 10¹⁴ to 10¹⁵ — because a more complete cancellation is a more complete cancellation. Which is this essay restated: an orthogonality residual is not a measurement of a quantity with digits. It is a measurement of the rounding the algorithm left behind, and it is supposed to have no significant digits of its own.

The general recommendation survives, narrowed. κ is informative wherever the numerator can vary — a residual b − Ax, a trace probe, a near-degenerate determinant, all of which the site’s own census tabulates — and uninformative wherever normalisation pins it, which is every orthogonality check here. That distinction is the number worth printing, and it is a property of the quantity rather than of the run.

assertTheInnerProductDiagnosticIsTheResidualInverted measures the whole table and requires the numerator to be pinned, κ to equal the answer inverted, and the better residual to carry the worse conditioning.

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.