Vector-radix FFT algorithm

The vector-radix FFT algorithm, is a multidimensional <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (FFT) algorithm, which is a generalization of the ordinary <a href="/facts/Cooley%E2%80%93Tukey_FFT_algorithm/03VB7JrC">Cooley–Tukey FFT algorithm</a> that divides the transform dimensions by arbitrary radices. It breaks a multidimensional (MD) <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> (DFT) down into successively smaller MD DFTs until, ultimately, only trivial MD DFTs need to be evaluated.
The most common multidimensional <a href="/facts/Fast_Fourier_transform/caT7UUCh">FFT</a> algorithm is the row-column algorithm, which means transforming the array first in one index and then in the other, see more in <a href="/facts/Fast_Fourier_transform/caT7UUCh">FFT</a>. Then a radix-2 direct 2-D FFT has been developed, and it can eliminate 25% of the multiplies as compared to the conventional row-column approach. And this algorithm has been extended to rectangular arrays and arbitrary radices, which is the general vector-radix algorithm.
Vector-radix FFT algorithm can reduce the number of complex multiplications significantly, compared to row-vector algorithm. For example, for a 
 
 
 
 
 N
 
 M
 
 
 
 
 {\displaystyle N^{M}}
 
 element matrix (M dimensions, and size N on each dimension), the number of complex multiples of vector-radix FFT algorithm for radix-2 is 
 
 
 
 
 
 
 
 2
 
 M
 
 
 −
 1
 
 
 2
 
 M
 
 
 
 
 
 N
 
 M
 
 
 
 log
 
 2
 
 
 ⁡
 N
 
 
 {\displaystyle {\frac {2^{M}-1}{2^{M}}}N^{M}\log _{2}N}
 
, meanwhile, for row-column algorithm, it is 
 
 
 
 
 
 
 M
 
 N
 
 M
 
 
 
 2
 
 
 
 log
 
 2
 
 
 ⁡
 N
 
 
 {\displaystyle {\frac {MN^{M}}{2}}\log _{2}N}
 
. And generally, even larger savings in multiplies are obtained when this algorithm is operated on larger radices and on higher dimensional arrays.
Overall, the vector-radix algorithm significantly reduces the structural complexity of the traditional DFT having a better indexing scheme, at the expense of a slight increase in arithmetic operations. So this algorithm is widely used for many applications in engineering, science, and mathematics, for example, implementations in image processing, and high speed FFT processor designing.

Vector-radix FFT algorithm open-in-new

Vector-radix FFT algorithm