Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

All reduce — where it appears

A collective in which every processor contributes a value and every one receives the combined result, costing about log₂p rounds.

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

Also named here as communication avoiding — the same set of essays touches all of them, so they are one junction rather than several.

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.

Communication avoidingAsymptotic analysisBackward stabilityBlock transferBroadcastCholesky qrCondition numberGram matrixLatencyMatrix multiplicationMemory hierarchyNormal equations

All concepts