A new matrix approach to real FFTs and convolutions of length \(2^k\) (Q2369946): Difference between revisions

With these very interesting results, the authors have broken the record set by \textit{R. Yavne} [Proc. AFIPS Fall Joint Comput. Conf. 33, 115--125 (1968)] for the lowest exact count of real additions and multiplications to compute a discrete Fourier transform (DFT) of order \(2^k\) with \(k\geq 8\). Nowaday, the fast Fourier transform (FFT) of R. Yavne is called split-radix FFT. Using recursive matrix factorization, the authors present modified split-radix FFTs that compute DFTs with real input vectors with about 6\(\;(SOT)\), a new trigonometric matrix for efficient computing of real FFTs and real convolutions of order \(2^k\). The new method for computing of real FFTs of order \(2^k\) depends on a recursive matrix factorization of SOT and attains fewer arithmetic operations. As an application, these results are used for efficient computation of real convolutions. Finally, it is shown that DFTs of Fermat prime order can be computed in fewer additions than previously available algorithms. Numerical tests show the high performance and numerical stability of these new modified split-radix FFTs. Fortran programs of these FFTs and convolutions are available via internet. Remark of the reviewer: A different approach to these modified split-radix FFTs can be found in \textit{S. G. Johnson} and \textit{M. Frigo} [IEEE Trans. Signal Process. 55, No. 1, 111--119 (2007)].