Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Blocking — where it appears

Grouping a matrix algorithm's work into blocks of columns, so that most of its arithmetic is matrix-matrix products that reuse data in fast memory. It changes the order of the rounding as well as the speed, which is why a blocked factorisation's accuracy is a separate measurement from its cost.

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

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 errorFlop countHouseholder reflectionMatrix multiplicationOrthogonalityQR factorisationUnit roundoffExact ground truthOrthogonal invariant

All concepts