Exploiting Symmetries of Small Prime-Sized DFTs

Small prime-sized discrete Fourier transforms appear in various applications from quantum mechanics, material sciences and machine learning. The typical implementation of the discrete Fourier transform for such problem sizes is done as a cyclic convolution using algorithms like Rader or Bluestein. However, these approaches exhibit extra computation and expensive data movement. In this work, we present an alternative method by casting the Fourier transform as a direct symmetric matrix-vector multiplication. Exploiting the symmetries of the Fourier matrix and using knowledge from dense linear algebra, we present an implementation that reduces the amount of computation and requires less memory usage. We show that this approach achieves up to 2x performance gains on Intel and AMD architectures, compared to implementations offered by Intel MKL and FFTW that use Rader and Bluestein.