05 Advanced: Build Your Own Matrix Class

April 2026 (447 Words, 3 Minutes)

Goal

Rebuild the part of NumPy you have been depending on — first in Python, then in C++ — and measure exactly how much engineering NumPy and Eigen have done on your behalf. You implement three matmul variants per language (entry-wise, column-by-column, outer-product), benchmark them, and compare against numpy.matmul and Eigen::Matrix. The takeaway is a four-line answer to why the libraries are fast.

This is an optional / advanced deep-dive. Plan for 1–2 weeks. Reflection-only deliverable (no graded points). Do this after you have finished D1–D4.

Get the Template

hs-aalen-software-engineering/linalg-from-scratch-template is the public template repository for this exercise. Click the green “Use this template” button on GitHub to create your own copy under your account, or fork it — either works.

Open your copy in GitHub Codespaces (the repo includes a Devcontainer that pre-installs Python, uv, g++, CMake, Eigen, and Catch2 — you don’t install anything yourself), or open it locally with VS Code’s Dev Containers extension.

Start with docs/00-getting-started.md inside the repo and follow chapters 1 through 9 in order.

What You Will Do

1. Build a Matrix class in Python — flat row-major storage, slicing, transpose, equality. Vectors are matrices of shape (n, 1) or (1, n); no separate Vector class.
2. Write unit tests with pytest — first time using pytest in this course. Add three of your own tests after the starters pass.
3. Implement three matmul variants in Python — matmul_entrywise, matmul_columnwise, matmul_outerproduct. Same answer, different memory and dispatch patterns. Verifies Exercise 6.4 of the linear algebra companion experimentally.
4. Benchmark Python runtime and memory — time.perf_counter plus tracemalloc, median of 5 runs. Plot on log–log axes.
5. Compare to NumPy — typically a 100–1000× speedup; explain why in four sentences.
6. Build the same Matrix class in C++ — std::vector<double> storage, operator(), transpose, slice. Heavy scaffolding so you don’t fight syntax.
7. Implement three matmul variants in C++ — matmul_ijk (naive), matmul_ikj (cache-friendly), matmul_eigen (Eigen wrapper via Eigen::Map). Build at -O0, -O2, and -O3 and compare.
8. Compare to Eigen — typically a 5–50× gap; explain expression templates, cache blocking, vectorisation, and BLAS dispatch.

Deliverables (AI Diary entry — D5 §9)

The single deliverable is the ai_diary.md reflection in your classroom repo. It expects answers to five questions, all backed by your own benchmark numbers:

• Which Python matmul variant was fastest, and did you predict it correctly?
• Did C++ matmul_ikj beat matmul_ijk as expected? Explain in terms of cache lines and stride.
• NumPy vs your best Python matmul — how big is the gap? List three things NumPy does that you don’t.
• Eigen vs your best C++ matmul — how big is the gap? Identify expression templates, cache blocking, vectorisation, BLAS dispatch.
• For a one-shot 1024×1024 matrix multiplication in production, what would you actually do — and why?

You also produce one results/comparison.png plot showing pure Python (best variant), NumPy, naive C++ at -O3, cache-friendly C++ at -O3, and Eigen on log–log axes.

Reference

• Lecture 5 — Inside the Transformer
• Chapter 5 — Geometric Foundations
• Chapter 7 — Understanding Attention
• D1 Matrix Drills — the cat-sat-on-it [12%, 40%, 16%, 11%, 20%] weights this exercise’s tests reuse
• D2 NumPy for Transformers — the NumPy notebook this exercise builds on
• Linear algebra companion — prompts/lecture-ideas/lecture_5/exercises/linear_algebra_for_transformers_exercises.md, Exercise 6.4 (three views of $AB$) and Chapter 12 (outer products)