China
Africa
Explore chapters and articles related to this topic
Roundoff Error Analysis for Fast Trigonometric Transforms
Published in George Anastassiou, Handbook of Analytic-Computational Methods in Applied Mathematics, 2019
Manfred Tasche, Hansmartin Zeuner
This matrix is unitary, too. Sometimes, Fn(0):=Fn is called even Fourier matrix. In the following we show that the split–radix FFT is based upon a synthesis of even and odd DFTs. In other words, the split–radix algorithm splits recursively Fn into Fn1⊕Fn1(1) and then Fn1(1) into Fn2⊕Fn2.
Fast Fourier Transforms
Published in R. Sastry Vedam, Mulukutla S. Sarma, Power Quality, 2017
R. Sastry Vedam, Mulukutla S. Sarma
According to Reference 22, the split-radix FFT algorithm has an efficiency exceeding that of a radix-8 FFT, a size comparable to that of a radix-4 FFT, and the flexibility of a radix-2 FFT. They included in the appendix of their paper example Fortran programs for the decimation in frequency and time algorithms.
Design of a modern fast Fourier transform and cache effective bit-reversal algorithm
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
The Fastest Fourier Transform in the West [16] is a very popular library offering various DSP algorithms. The only weakness of this library is that its prime time of development was when vectorization was starting to make a name for itself. Before vectorization making efficient FFT algorithms meant reducing the number of arithmetic operations. The most popular way of achieving this was by utilizing split-radix FFT, especially in the FFTW version, greatly lowering operation count [17]. These split-radix implementations usually break the regularity of the Cooley–Tukey algorithm to combine multiple radix-R parts into one stage resulting in fewer instructions, and the FFTW version is the one that was the best in this discipline [18]. Even if this sounds like an excellent starting point for creating an efficient FFT algorithm, the split-radix version has worse scaling with vectorization due to breaking symmetries and regularity, which the standard Cooley–Tukey version offers. Still, FFTW is definitely the most popular FFT library and is very fast on smaller problem sizes; even though sequential performance is lacking in comparison to the aforementioned libraries, FFTW offers scalable multi-threading achieved with Open MP.