Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cache — where it appears

The small fast memory a processor reads from before it reaches main memory. Its size sets the block size of every blocked algorithm here, and whether a computation fits in it decides the cost far more than the operation count does.

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

10²10³10⁴10⁵matrix size ncountoperations, bothwords, unblockedwords, blocked (b = 6)the answer does not move‖PA − LU‖/‖A‖, unblocked2.8·10⁻¹⁶‖PA − LU‖/‖A‖, blocked2.8·10⁻¹⁶difference between them0the dashed curve is both orderings' operation countthe solid pair is what they cost

The same arithmetic at a different price

A blocked and an unblocked elimination perform 72,568 operations each — the same operations, associated differently — choose the same pivots, and return a factorisation identical to the last bit: ‖PA − LU‖/‖A‖ = 4.487946226420872·10⁻¹⁶ in both. One of them moves 41,332 words between fast and slow memory and the other moves 19,476.

cost · blocking 110¹10⁴10⁵block size bwords movedthe count: √(M/3) = 5measured best: b = 8words movedat the best block1.6·10⁴at b = 13.9·10⁴at b = 243.9·10⁴derived from M with no measurement, and scannedthe two agree

A block size is a property of the machine

Three lines of counting say the best block size is √(M/3). Scanned over every integer at five fast memories, the measured optimum is √M − 2 — exactly, at all five. The count has the right scaling and the wrong constant, low by a factor of 1.56, and the wrong form: the answer is affine in √M rather than proportional to it.

cost · blocking

Named alongside it

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

Blocked algorithmData movementFlop countLoop orderMemory hierarchyCommunication lower boundFitted exponentLU factorisationResidual

All concepts