Optimized Matrix Multiplication

Overview

Textbook matrix multiplication requires O(n³) scalar multiplications. In 2022, DeepMind's AlphaTensor discovered a sub-cubic decomposition for multiplying a 4×5 matrix by a 5×5 matrix using 76 scalar multiplications instead of 80.

This project implements the AlphaTensor decomposition in modern C++, comparing its practical execution performance against Strassen-Winograd and a baseline triple-loop on modern CPU architectures.

Implemented Algorithms

All algorithms operate on contiguous, row-major float* buffers to eliminate pointer chasing and maximize memory locality:

Implementation Details

1. Strassen-Winograd Recursion

Computes 2×2 sub-matrix blocks using 7 intermediate products ($M_1$ through $M_7$). Once sub-block dimensions drop below a threshold, execution switches to the baseline algorithm to avoid recursion overhead.

2. AlphaTensor Decomposition

The 4×5×5 decomposition partitions matrices into block grids, evaluating 76 bilinear combinations ($h_1$ through $h_{76}$) before linearly reassembling the 20 output blocks.

3. Bit-Exact Verification Oracle

To catch any indexing or sign bugs, the harness benchmarks fast paths against naive multiplication using small integer inputs that fit exactly into floating-point mantissas, verifying complete bit-for-bit equality.

Benchmark Execution

# Compile with aggressive optimization
g++ -O3 deepmind_winograd_matrix_multiplication.cpp -o matrix_mult
./matrix_mult

Key Findings

1. Arithmetic vs. Memory Trade-Off: Reducing scalar multiplications by 5% introduces additional matrix additions and temporary buffer allocations.
2. Cache Hierarchy Impact: At small-to-medium matrix sizes, memory bandwidth and cache alignment influence total execution time more heavily than arithmetic operation counts.

Tech Stack Summary

• Language: C++17
• Compiler: GCC / Clang (-O3)
• Focus Areas: Tensor Decomposition, Cache Optimization, Numerical Correctness, Hardware Profiling