MFFT

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.