fmm-fft

Parallel FMM Accellerated FFT on CPUs using OpenMPI. Based on the works of Edelman et. al..

Authors

• Amarnath Karthi
• Chahak Mehta

Introduction

Traditional distributed Fast Fourier Transforms (FFTs) require 3 all-to-all communications which cause severe communication bottlenecks. FMM-FFT uses the Fast Multipole Method to approximate the solutions of the FFT, thereby reducing the communication required.

Dependencies

• FFTW3
• OpenMPI
• OpenMP

Codes

• src/fftw_mpi.c : Distributed FFT
• src/fmmfft.c : Distributed FMM Accellerated FFT
• src/fmmfft_error.c : Comparison of FFT and FMM-FFT outputs

Installation

1. Edit makefile and change the -L and -I in the local target.
2. make local
3. Run the out file.

References

[1] The Future Fast Fourier Transform?, by Edelman et. al. , SIAM Journal on Scientific Computing. SIAM J Scientific Computing 20 1094-1114 (1998)

[2] Re-Introduction of Communication-AvoidingFMM-Accelerated FFTs with GPU Acceleration, by Langston et. al. , IEEE Conference on High Performance Extreme Computing (HPEC '13)

TODO:

• Add headers for FMM-FFT functions.