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

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.

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.