Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Matrix multiplication — where it appears

Forming the product of two matrices, which costs 2mnk operations by the definition and is the operation every dense factorisation is rearranged to spend its time in. A product moves far fewer numbers per operation than a matrix–vector product does, which is why a blocked algorithm runs at a large fraction of a machine's peak where an unblocked one runs at a few per cent.

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

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 what a block storesnumbers in T, block of 11numbers in T, block of 16136‖QᵀQ − I‖ there3.9·10⁻¹⁵10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶block size‖QᵀQ − I‖124816T perturbed by 10⁻⁶T as computed1, 3, 10, 36, 136 computed numbers in the triangleand a factor of five in what they produce

A triangle where the scalar was

Every level-3 QR assembles a block of reflectors into Q = I − Y T Yᵀ, and T is computed by a recurrence whose inputs are its own previous columns. A block of sixteen carries 136 computed numbers where sixteen separate reflections carry sixteen. The orthogonality it produces is 3.9·10⁻¹⁵ against the single reflector's 7.8·10⁻¹⁶ — a factor of five for a hundred and thirty-six times as many things that have to be right.

orthogonality · Householder

Named alongside it

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

All reduceAsymptotic analysisBackward errorBlock transferBlockingBroadcastCommunication avoidingExact ground truthFlop countHouseholder reflectionLatencyMemory hierarchy

All concepts