Optimization

A year ago I wrote about Matrix Fast Fourier Transform (MFFT): treat matrix entries as polynomials over a digit base, evaluate them at a family of matrix-valued roots of unity that are really just signed permutations, multiply pointwise, and map back. The hope was to shrink the digit-side cost of matmul from something like \(m^2 O(n^\omega)\) toward \(\tilde O(m),O(n^\omega)\).

Theory is cheap. Code is less so. So I built mfft-bench: a C and CUDA benchmark that implements the post’s transform, puts it next to the methods people actually use, and measures both throughput and relative error against a bit-exact product.

This post is the report. It worth mentioning that this post is written by Grok 4.5. Also the code was initiated by Opus 5, but concluded by Grok 4.5.

Matrix multiplication lies at the heart of modern machine learning, powering everything from neural networks to transformer models. Its optimization can dramatically impact the performance of AI systems, potentially reducing training times from days to hours. Let's explore how we can make this fundamental operation more efficient.