FFT Accelerated Convolutions
Using frequency-domain multiplication via FFT (Fast Fourier Transform) to compute linear convolutions more efficiently than direct time-domain methods, especially for large kernels or long signals common in ML (Machine Learning) workloads.
FFT (Fast Fourier Transform) Accelerated Convolutions exploit the convolution theorem: convolution in the time/spatial domain becomes elementwise multiplication in the frequency domain, so by transforming inputs and kernels with an FFT, multiplying pointwise, and inverse-transforming, one can compute convolutions with asymptotic and practical speedups versus direct sliding-window methods — particularly when kernel or input sizes are large or when batched, high-throughput computation (e.g., on GPUs) amortizes FFT overhead.
In-depth context for AI practitioners: the method replaces O(N·K) direct convolution work with FFTs whose cost is roughly O(N log N) (for suitably chosen transform length), making it attractive for large 1D/2D/3D convolutions, very wide kernels, or long temporal sequences. Key implementation details matter: linear convolution requires zero-padding to avoid circular-wrap, and practical pipelines use overlap-add or overlap-save blocking to handle streaming/large inputs while controlling memory and transform sizes. On modern accelerators, batched FFTs (using libraries like cuFFT or FFTW) and fused pointwise kernels reduce memory traffic; however, transform overhead, extra memory for complex tensors, numerical precision (real→complex→real rounding), and boundary handling can make FFT-based approaches suboptimal for small kernels where algorithms such as Winograd or optimized direct GEMM-based im2col dominate. FFT acceleration also interacts with other AI techniques — e.g., FFT-based cross-correlations in attention, efficient frequency-domain parameterizations, and some compressive or low-rank approximations — and is often chosen after careful profiling of kernel sizes, batch shapes, and memory bandwidth on the target hardware.
First uses date back to the FFT algorithm and convolution theorem adoption in signal processing (Cooley & Tukey popularized FFT in 1965); FFT-based convolution has been used in DSP since the 1960s–1970s and became prominent in ML workloads in the early 2010s as large-scale CNNs, efficient GPU FFT libraries, and batched implementations made frequency-domain methods practical (notably in papers and implementations around 2013–2015).
Key contributors and implementations include J. W. Cooley and J. W. Tukey (coalescing FFT into practical algorithms), Matteo Frigo and Steven G. Johnson (FFTW), NVIDIA (cuFFT and GPU-optimized routines), and ML researchers who adapted FFT methods to deep learning such as Mathieu, Henaff, and LeCun (work on FFTs for convolutional networks). More recent practical comparisons and alternatives were advanced by researchers demonstrating Winograd and GEMM-based wins (e.g., Lavin & Gray for Winograd) and by framework teams integrating FFT- and winograd-based kernels into libraries for TensorFlow and PyTorch.
