Experiments on Speeding Up the Recursive Fast Fourier Transform by using AVX-512 SIMD instructions

The Fast Fourier Transform is probably one of the most studied algorithms of all time. New techniques regarding hardware and software are often applied and tested on it, but the interest in FFT is still large because of its applications - signal and image processing, numerical computations, etc. In this paper, we start from a trivial recursive version of the algorithm and we speed it up using AVX-512 Single Instruction Multiple Data (SIMD) instructions on an Intel i7 CPU with native support to AVX-512. In particular, we study the impact of two different storage choices of vector of complex numbers: block interleaving and complex interleaving. Experimental results show that automatic vectorization provides a 10.65% (∼ 1.12×) speedup, while with vectorization done by hand the speedup reaches 33.78% (∼ 1.51×). We have made our code publicly available, which could be helpful for SIMD instructions teaching purposes