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 3 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 96 × 64, κ = 10⁸blocks of eight, final1.4·10⁻¹⁴their root-sum-square1.2·10⁻¹⁴one at a time, final2.9·10⁻¹⁴081624324048566410⁻¹⁵10⁻¹⁴10⁻¹³columns factorised‖QᵀQ − I‖sum of the blocks' ownone reflector at a timeblocks of eightroot-sum-squareeach block is one factor, each reflector anotherthe departure grows with the square root of the count

Eight blocks and sixty-four reflections

One block of sixteen reflectors, assembled as I − Y T Yᵀ, departed from orthogonality five times as far as a single reflection, and the question was whether a factorisation of many blocks multiplies that factor. It does not. On 96 × 64 matrices eight blocks of eight end at 1.42·10⁻¹⁴ — within a fifth of the root-sum-square of their own departures, and less than half their sum — while the same factorisation taken one reflector at a time ends at 2.91·10⁻¹⁴. A block departs more than a reflector, and there are an eighth as many of them. And a nearly dependent column that swells the triangle's entries to 10²⁶ costs the product nothing.

orthogonality · Householder

Named alongside it

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

Backward errorBlockingFlop countHouseholder reflectionOrthogonalityQR factorisationUnit roundoffAll reduceAsymptotic analysisBlock transferBroadcastCommunication-avoiding

All concepts