Matrix multiplication as computation

Reading: Golub & Van Loan §1.1–1.3, pp. 2–33.

By the end of this week you should be able to

• Express a matrix product in dot-product, saxpy, and outer-product form, and say which is which from the loop nesting.
• Count flops for the basic kernels and classify an operation as BLAS level 1, 2, or 3.
• Explain why two loop orderings with identical arithmetic can differ by an order of magnitude in runtime.

Algorithms introduced

• The six loop orderings of matrix multiplication
• Blocked matrix multiplication
• Strassen's algorithm

Where this shows up in AI

Arithmetic intensity is why every GPU kernel behind a neural network is restructured into blocked, level-3 operations. Understanding the memory hierarchy explains far more about training throughput than flop counts do.

Materials