MR-Butterfly—A fast Fourier Transform Algorithm Based on MapReduce

Abstract

Based on the research and analysis of the butterfly computing structure of the Cooley-Tukey algorithm, a fast Fourier transform algorithm MR-Butterfly for large data is proposed in this paper. The algorithm makes full use of the fast Fourier leaf-changing butterfly calculation structure, which can be used to determine the characteristics of the Cooley-Tukey butterfly calculation unit for the complex multiplication and complex addition operations in batch processing. The MR-Butterfly algorithm does not need to deal with synchronization and communication. The algorithm has the advantages of simple structure, robustness, universality and extensibility. The experimental part verifies the validity of the algorithm by using the test data with large data volume.