BlackNUFFT: Modular customizable black box hybrid parallelization of type 3 NUFFT in 3D

Many applications benefit from an efficient Discrete Fourier Transform (DFT) between arbitrarily spaced points. The Non Uniform Fast Fourier Transform reduces the computational cost of such operation from O(N^2) to O(N logN) exploiting gridding algorithms and a standard Fast Fourier Transform on an equi-spaced grid. The parallelization of the NUFFT of type 3 (between arbitrary points in space and frequency) still poses some challenges: we present a novel and flexible hybrid parallelization in a MPI-multithreaded environment exploiting existing HPC libraries on modern architectures. To ensure the reliability of the developed library, we exploit continuous integration strategies using Travis CI. We present performance analyses to prove the effectiveness of our implementation, possible extensions to the existing library, and an application of NUFFT type 3 to MRI image processing.