Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cache-oblivious — where it appears

Describes an algorithm that moves little data across a memory hierarchy without being told the size of any cache. It divides its problem into pieces of every size, so whatever caches a machine has, some level of the division fits each of them.

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

110¹10²10⁵block size bwords movedbest block: b = 10the recursion: no block size126,742 wordsbest block, scanned1.1·10⁵the recursion1.3·10⁵recursion ÷ best1.2M = 144 words; the recursion never reads it1.16× the best of 24 blocks

The recursion that was never told the memory

A blocked elimination has to be tuned to its fast memory, and tuned to one memory it costs up to 2.9 times the best at another. A recursive elimination splits the columns in half down to one and reads no memory size at all. On eight fast memories from 36 to 576 words it moves between 0.94 and 1.28 times the words of the best tuned block, with the same 585,200 operations and the same pivots — and on a machine with two caches it beats the block tuned to either cache on six machines of seven.

cost · Blocking 110¹123base case, columnswords ÷ the best block's√M − 2 = 10M = 144M = 144base of one1.2panels ≤ 10, worst1.2panels of 123the base case is a block size, rounded to a halvingand it has the block's cliff at √M − 2

The block size a recursion still has

A recursive elimination is sold as having no block size, and every real one switches to plain loops below some width. Swept over that width, the traffic is a staircase with its steps at the halvings of n, and its cliff sits where the blocked elimination's does — the first panel wider than √M − 2 moves 1.53 to 4.47 times the words, on six memories of six. On three caches the innermost decides, and a third cache costs every tuned block up to 14 per cent and the recursion nothing.

cost · Blocking -12-10-8-6-4-2024681011.522.533.5leaf width minus (√M − 2)words ÷ pure recursionM = 64M = 144M = 256the edge is the same column at every memoryand the cheapest leaf sits on it

The leaf that sits on the edge

A recursive elimination's base case was found to be a block size in disguise, with a cliff where the blocked elimination's is, and the choice read as a trade: the processor wants wide leaves, the cache wants narrow ones. Measured at every width rather than at the halvings of 96, there is no trade inside the edge. Leaves exactly √M − 2 wide are the cheapest the recursion can have in words as well as calls — 0.81, 0.80 and 0.84 of the pure recursion's traffic at 64, 144 and 256 words — and one column wider moves 1.77 to 3.15 times it. And a matrix of 100 columns, which halves unevenly, meets the cliff in two steps rather than one.

cost · Blocking

Named alongside it

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

Blocked algorithmData movementFlop countLU factorisationMemory hierarchyRecursive factorisationPartial pivoting

All concepts