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
|
