Multi Dimensional FFT’s
Multi-dimensional FFT’s are very common and the most important for parallel computing as they are more computationally intense
- Images naturally give two dimensional FFT’s
Take a 2d2 by 2d1 FFT in two dimensions and label it by a d digit binary number with d=d1+d2
Then all discussions are essentially identically to one dimensional FFT with dimension d
The algorithm is different but communication issues and strategy of re-ordering binary index are same
In particular one would normally first do the d1 transform in say low d1 bits and then swap upper d2 bits into lower part of d digit label -- now do d2 digit transform. This way one again only gets communication in swap and otherwise one has perfectly one dimensional parallel FFT’s inside each processor