New polynomial transform algorithms for fast DFT computation

Polynomial transforms defined in rings of polynomials, have been introduced recently and shown to give efficient algorithms for the computation of two-dimensional convolutions. In this paper, we present two methods for computing discrete Fourier transforms (DFT) by polynomial transforms. We show that these techniques are particularly well adapted to multidimensional DFTs and yield algorithms that are, in many instances, more efficient than the fast Fourier transform (FFT) or the Winograd Fourier Transform (WFTA).