Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Communication avoiding — where it appears

Rearranging a computation to move fewer words or send fewer messages, usually by spending arithmetic, memory or accuracy instead. The currency it saves is words moved or messages sent, and it is bought with arithmetic, memory or accuracy — so a claim that it is free is a claim that has not been costed.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

10²10³10⁴10⁵10⁶10⁷10⁸10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²condition number‖QᵀQ − I‖one passsweeptwicetreewhat the second pass removesfitted slope, one pass2fitted slope, two passes0.96rounds, two passes6rounds, the sweep24one pass squares the condition numberand two do not

Doing it twice

Cholesky QR squares the condition number — a fitted slope of 1.95 in κ against the Householder sweep's 1.00. Run the identical routine a second time on the Q it returned and the slope is 0.93, the orthogonality is at or below the sweep's at every κ, and the price is one more all-reduce.

cost · communication 10²11.251.51.7522.25processorstraffic saved, as a factorthe √4 the law promisesbreak-evenmeasureda limit is not a sizesaving at p = 640.88saving at p = 5761.4what the law promises2memory, as a factor4a loss at sixty-four processorsand 72% of the law at five hundred

Memory bought with messages

Holding four copies of the data instead of one is supposed to cut a matrix multiplication's communication by √4. Measured on a machine of 64 processors it costs 14% more traffic; at 576 it saves 44%, which is 72% of what the law promises. The memory is exactly four times, and that part is not asymptotic.

cost · communication

Named alongside it

The objects these essays reach for when they reach for this one.

All reduceAsymptotic analysisBackward stabilityBlock transferBroadcastCholesky qrCondition numberGram matrixLatencyMatrix multiplicationMemory hierarchyNormal equations

All concepts