Parallel fast Fourier transform algorithm based on binary fat tree network
一种基于二叉胖树模型的并行FFT算法

The binary fat tree is a network topology which is prone to accomplish butterfly computing. According to this feature, a logical model for binary fat tree was constructed at first, and then a parallel Fast Fourier Transform algorithm based on it was developed. In this algorithm, balance of load was achieved in the process, and time complexity was reduced compared with serial algorithm. At last the algorithm was implemented in cluster and MPI, and experimental data was analyzed.