The message and the word

The cost field exists because counting arithmetic stopped predicting anything. Its model counts words moved between a fast memory of M words and a slow one, and with that counter it measured the field’s founding result: a blocked and an unblocked elimination perform exactly 72,568 operations, choose the same pivots, return a residual agreeing to every digit, and move 41,332 words against 19,476.

That model has a shape it cannot express, and the field wrote the gap down as a deferral: parallel communication counted in messages rather than words. A machine with p processors charges twice — once for how much data crosses the network, and once for how many times the processors have to stop and talk to each other. The second is latency, it is of the order of a microsecond however few words the message carries, and a word of bandwidth is of the order of a nanosecond. A thousand words in one message and one word in one message cost about the same. One word in a thousand messages costs a thousand times more.

No duration appears anywhere in this essay, for the reason the field states about its own counts: a duration is a fact about a machine and a count is a fact about an algorithm.

The model, and what is counted #

p processors, each holding a horizontal slice of a tall matrix. Three quantities, counted by a counter the algorithms call rather than by a formula written beside them:

• rounds — communication steps on the critical path, which is the latency cost;
• messages — point-to-point sends in total;
• words — numbers crossing the network, which is the bandwidth cost.

The calls sit next to the arithmetic they belong to, because that is the only place a model like this can be wrong. A count summarised at the end of a function is a claim about what a distributed implementation would do; a count next to the line that needs the data is a description of it.

Three factorisations of one matrix #

Householder, column by column. Each column needs its norm over all p slices, which is a reduction, and the reflector’s inner products with the trailing columns need another. n columns, log₂p levels each: n log₂p rounds. This is the algorithm matrix.js implements and it is the one that talks the most.

The reduction tree. Factorise each slice locally, then combine R factors pairwise up a binary tree: log₂p rounds, whatever n is. The breadth phase measured its arithmetic: 1.65·10⁻¹⁵ backward error against a Householder sweep’s 9.95·10⁻¹⁵ on a 512×12 matrix at κ = 7,151, with the error not growing with the depth of the tree — 3.38, 4.26, 1.65, 1.48·10⁻¹⁵ at depths one to four.

And Cholesky QR. Form G = AᵀA — one reduction of an n×n matrix — factor G = RᵀR, set Q = AR⁻¹. One reduction, which is the fewest any factorisation can use.

The sweep’s rounds are exactly n times the tree’s at every p — 12 here — because the sweep synchronises once per column and the tree once per level. And the words do not separate them at all: the sweep and the tree send the identical number, and the method with the fewest rounds sends nearly twice as many as either, because a Gram matrix is a square and an R factor is a triangle.

A model that counts only words ranks these three wrong. That is the deferral, discharged: the whole reason the tall-skinny QR was developed is invisible to the field’s existing counter, and the refusal this essay publishes is fed exactly that — the claim that counting words separates the sweep from the tree, on a case where the two counts are equal.

And the ranking does not depend on the machine, which is the part worth checking rather than assuming.

Both ratios are constants. Across p = 2, 4, 8, 16 and 32 the sweep’s round count is n = 12 times the tree’s at every one — 12/1, 24/2, 36/3 and 60/5 — and the Cholesky route’s word count is 1.85 times the other two at every one: 144/78, 432/234, 1008/546, 4464/2418. Neither ratio drifts by so much as a per cent across a factor of sixteen in the processor count.

So the choice between these three is settled once, not per machine. Both counters grow with p — rounds as log p, words as p log p — and they grow at the same rate for all three methods, so nothing about scaling up reorders them. That is a stronger statement than the section made and it is the one a caller needs: the tree’s advantage in rounds is a factor of n, fixed by the matrix rather than by the machine, and the Cholesky route’s penalty in words is a factor of 1.85, fixed by the shape of a square against a triangle. Neither number is something a larger cluster can change, so a decision taken on eight processors is the right decision on eight thousand — and the quantity that does decide it, n, is the one a reader would have expected to be irrelevant to a communication argument.

And the tree does more arithmetic, not less #

A communication-avoiding algorithm is not a cheaper algorithm. The tree performs p local factorisations of (m/p)×n blocks plus p − 1 combines of 2n×n blocks, which by the standard operation count 2mn² − 2n³/3 comes to 178,560 against the sweep’s 146,304 at m = 512, n = 12, p = 8 — 22% more.

It is worth having anyway because the arithmetic is local and the communication is not, which is the whole premise of the field. But it is a trade, it is the opposite way round from what “avoiding” tends to suggest, and it is one of this family’s published refusals.

The price of the fewest messages #

The orthogonality is measured the same way for all three: ‖QᵀQ − I‖ with Q = AR⁻¹. That is a uniform quantity and it is the one a real code meets — Cholesky QR forms Q exactly this way, and a least-squares solve through any of these R factors is exactly this Q applied to a right-hand side. It is also the quantity two Gram–Schmidts is built around, so the three methods here are measured on the same axis as the two there. Comparing each method’s own internal Q would be comparing three different objects, and would let the method that never forms one escape the comparison.

The slope is the assertion rather than any single value, because a slope is a claim about the mechanism and a number at one κ is a claim about one matrix.

Which is a square this site has met twice already #

κ² is not a new quantity here. The road that squares the problem measures what forming AᵀA does to a least-squares problem: the condition number squares, and below ε = √u the Gram matrix of a perfectly ordinary matrix comes out exactly singular — every entry of AᵀA equal to one.

Cholesky QR forms AᵀA. That is not an analogy or a family resemblance; it is the same line of arithmetic, appearing in a different field for a different reason, with the same consequence. What is new is why somebody would do it: not because the normal equations are the obvious derivation, but because AᵀA is a sum over the slices and therefore one reduction, and one reduction is the minimum.

So the trade is not between speed and elegance. It is the same κ² this site has measured twice, being paid for a round trip.

Past the cliff: refuse, or lie, and it is erratic which #

Read the last two rows together. The method declines a matrix at κ = 3·10¹⁰ — the Gram matrix is numerically indefinite, Cholesky meets a nonpositive pivot, and there is nothing to return — and then succeeds on a harder matrix at 10¹², handing back a triangular factor whose implied Q is not orthogonal in any sense.

The failure that is safe is the refusal. The failure that is dangerous is the success, and which of the two happens is decided by rounding near a boundary rather than by the conditioning. This site has recorded that shape once before, in the mixed-precision field: near a threshold the outcome is genuinely erratic — at κu ≈ 6 the same format finishes 40× short at one matrix size and 7,000× at another. The refusal itself is a factorisation with nothing to pivot for’s subject, arriving here as a network decision rather than a definiteness test.

Both behaviours are asserted, and the assertion is written to require both. An assertion that the method refuses past the cliff would describe something that reliably declines, and it does not.

What this says about choosing a factorisation #

Three statements, in the order a decision would use them.

Count rounds, not words. On the shapes this essay draws, the word counts rank the three methods in an order that has nothing to do with what a machine charges for, and the round counts differ by a factor of n.

The tree is the answer for a tall matrix, and its cost is 22% more arithmetic, all of it local. Its backward error does not grow with the depth of the tree, which the breadth phase measured separately at depths one to four — so the reduction can be as deep as the machine is wide.

And Cholesky QR is usable exactly when κ² u ≪ 1, which is a computable condition and is the whole of its applicability. Where it holds, one reduction is genuinely one reduction and the method is excellent. Where it does not, the failure is either a refusal or an answer that looks like the others, and no amount of communication analysis will tell them apart.

Except that there is a repair, and it is priced in the same counters #

That is where the account usually stops, and it leaves out the thing production codes actually do: run it twice. Factor A = Q₁R₁, factor Q₁ = Q₂R₂, take R = R₂R₁. The first pass is inaccurate but it is a good preconditioner — Q₁’s condition number is about κ²u rather than κ, which is buying the accuracy back’s identity with a factorisation in place of a precision — so the second pass runs on a nearly orthogonal matrix and the product comes back orthogonal.

It works, and the surprise is how far it works: at κ = 10⁸ and 10¹⁰ the twice-run method matches the reduction tree, two and four decades past the cliff the single pass is confined to. A number that was 1.27 — no orthogonality whatever, the total loss the figure above records — becomes 3.7·10⁻⁷ for one more reduction.

And one more reduction is the whole of the objection. The counters this field exists to keep say what it costs: 8 rounds against the tree’s 4, and 1,920 words against 540. The one-reduction advantage that motivated the method in the first place does not survive its own repair — the repaired version is behind the reduction tree on both counters, by a factor of two and a factor of 3.6, and it is behind on the arithmetic as well, since it performs the whole factorisation twice.

So the ranking the essay set out to establish is not disturbed by the repair; it is confirmed by it. The tree is the answer for a tall matrix, and the case for Cholesky QR rests entirely on the single pass being enough — which is to say on κ²u ≪ 1, which is where the previous section left it.

One thing the repair cannot do is the failure that was called dangerous. Where the first pass refuses — κ = 3·10¹⁰ on this family, a nonpositive pivot at column seven — there is no Q₁ to factor again and the second pass never runs. Repeating repairs a wrong answer and inherits a refusal unchanged, which is the right way round: the safe failure stays, and the dangerous one is the one that gets fixed.

That last point is the one the field’s own habit is for. A method is chosen on a cost model; the cost model is right; and the quantity the cost model cannot see is the one that decides whether the answer is an answer. The residual is not the only thing worth printing next to a factorisation — for these three the residuals are equal to rounding, and ‖QᵀQ − I‖ is what separates them by eleven orders of magnitude.

What the model does not have #

Bandwidth and latency together. Real cost models are α + βw per message — a fixed cost plus a per-word one — and the interesting algorithms are chosen by minimising a weighted sum rather than either count alone. Everything here reports the two counts separately and refuses to weight them, because the weight is the machine and the site’s rule is that no duration appears in a cost claim.

Topology. The reduction tree here is binary and the network is assumed to be able to carry any pair of processors talking. A real machine has a topology, and a reduction on a torus costs differently from one on a fat tree.

And overlap. Nothing here models communication happening while arithmetic happens, which is the first thing any real implementation does and which changes what “critical path” means.

What the model assumes, and where it would be wrong #

A cost model is a claim about a machine, and the honest way to present one is with its assumptions where a reader can check them rather than in a footnote.

One reduction is log₂p rounds. That is a binary tree, and it assumes any pair of processors can talk at the same cost. A real machine has a topology; a reduction on a torus is a different count from one on a fat tree, and on a machine with hardware collectives it may be one round rather than log₂p. What survives topology is the ratio between the three methods, because all three pay the same per-reduction price and differ only in how many reductions they need.

The sweep needs one reduction per column. That is the standard distributed Householder QR, and it is the count that makes the ratio exactly n. A code that reformulates the sweep to reduce several columns at once — which is what a blocked panel factorisation does — moves that count down by the panel width, and the tree is then better by n/b rather than by n. That is a real and well-known refinement and it does not change the shape: the tree’s count contains no n at all.

And no message is charged for its own size. Real models are α + βw per message, and the interesting algorithms minimise a weighted sum of the two counts. Everything here reports the counts separately and refuses to weight them, because the weight is a property of a machine and this site’s rule for the whole cost field is that no duration appears in a cost claim.

Two things the model has no way to express, both of which a real implementation depends on: overlap, where communication happens while arithmetic does and the critical path is neither count alone; and memory hierarchy on each node, which is the quantity cost.js counts and which is orthogonal to everything here.

The three residuals, and why they are not the measurement #

Every figure in this essay prints ‖AᵀA − RᵀR‖/‖AᵀA‖ for the method it draws, and the numbers are 1.2·10⁻¹⁵, 8.2·10⁻¹⁶ and 1.2·10⁻¹⁶ at κ = 10³ — the Cholesky route’s is the smallest of the three.

That is not a paradox and it is the reason this essay exists in the form it does. R is the triangular factor of this matrix, to rounding, by all three routes; what differs is what happens when a right-hand side is solved through it, which is the quantity ‖QᵀQ − I‖ of the implied Q measures.

The site’s rule is that no decomposition is drawn without its residual printed, and this is the case where obeying the rule and stopping there would mislead. The badge says the factorisation is fine. The factorisation is fine. What is not fine is the basis it implies, and the field that measures orthogonality as a number rather than an adjective is the one that can say so.

What a decision would use #

Three statements, in the order a choice would need them.

Count rounds, not words. On these shapes the word counts rank the three methods in an order with nothing to do with what a machine charges for, and the round counts differ by a factor of n.

The tree is the answer for a tall matrix, at 22% more arithmetic, all of it local, with a backward error that does not grow with the depth of the tree — measured at depths one to four in this field already.

And Cholesky QR is usable exactly when κ²u ≪ 1, which is computable before the factorisation is attempted. Where it holds, one reduction is genuinely one reduction. Where it does not, the failure is either a refusal or an answer indistinguishable from the others by any residual, and no amount of communication analysis separates them.

What is left #

The 2.5D and communication-avoiding factorisations of square matrices, where the same analysis applies to LU and to matrix multiplication and where the lower bounds are genuinely deep — a result of the form no algorithm can send fewer than this many words is a different kind of statement from anything measured here.

And CholeskyQR2, which is the standard repair: run Cholesky QR twice, on the grounds that the second pass sees a matrix whose condition number is the square root of what the first pass had to deal with. It is two reductions rather than one, and whether the ‖QᵀQ − I‖ curve above flattens under it is a measurement this site could make and has not.

An algorithm chosen for what it moves #

Counting messages rather than operations changes which algorithm wins. The clearest instance in this phase is an orthogonalisation built entirely from matrix products, which does twice the arithmetic and needs no global communication at all.