Mathematics

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(N2) to O(NlogN) 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. Program summary Program Title: BlackNUFFT Program Files doi: http://dx.doi.org/10.17632/vxfj6x2p8x.1 Licensing provisions: LGPL Programming language: C++ External routines/libraries: deal.II , FFTW, PFFT Nature of problem: Provide a modular and extensible implementation of a parallel Non Uniform Fast Fourier Transform of type 3. Solution method: Use of hybrid shared distributed memory paradigm to achieve high level of efficiency. We exploit existing HPC library following best practices in scientific computing (as continuous integration via TravisCI) to reach higher complexities and guarantee the accuracy of the solution proposed.