A new matrix approach to real FFTs and convolutions of length 2ᵏ
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)].
- A new set of minimum-add small-n rotated DFT modules
- Fast computation of real discrete Fourier transform for any number of data points
- Fast Fourier transforms: A tutorial review and a state of the art
- Fast mixed-radix real Fourier transforms
- Real-valued decimation-in-time and decimation-in-frequency algorithms
- Simple FFT and DCT algorithms with reduced number of operations.
- Split-radix algorithms for length-p/sup m/ DFT's
- The design of optimal DFT algorithms using dynamic programming
- Quasiperiodic spectra and orthogonality for iterated function system measures
- On elliptic curves and random matrix theory
- Accurate pairwise convolutions of non-negative vectors via FFT
- Separation of variables and the computation of Fourier transforms on finite groups. II
- On the real complexity of a complex DFT
- Generating and searching families of FFT algorithms
- Blind image deconvolution using a banded matrix method
- Modified FFTs for Fused Multiply-Add Architectures
- Real-valued decimation-in-time and decimation-in-frequency algorithms
- A New Representation of FFT Algorithms Using Triangular Matrices
- Separation of variables and the computation of Fourier transforms on finite groups. II
- Multiplication
- The Tangent FFT
- The matrices form of 2FFT
- Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
- A survey of polynomial multiplications for lattice-based cryptosystems
This page was built for publication: A new matrix approach to real FFTs and convolutions of length \(2^k\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369946)
