Blocked algorithm — where it appears
Also named here as cache, flop count, loop order, memory hierarchy — the same set of essays touches all of them, so they are one junction rather than several.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
CacheData movementFlop countLoop orderMemory hierarchyCommunication lower boundFitted exponentLU factorisationResidual