Accelerating the nonequispaced fast fourier transform on commodity graphics hardware

We present a fast parallel algorithm to compute the nonequispaced fast Fourier transform on commodity graphics hardware (the GPU). We focus particularly on a novel implementation of the convolution step in the transform as it was previously its most time consuming part. We describe the performance for two common sample distributions in medical imaging (radial and spiral trajectories), and for different convolution kernels as these parameters all influence the speed of the algorithm. The GPU-accelerated convolution is up to 85 times faster as our reference, the open source NFFT library on a state-of-the-art 64 bit CPU. The accuracy of the proposed GPU implementation was quantitatively evaluated at the various settings. To illustrate the applicability of the transform in medical imaging, in which it is also known as gridding, we look specifically at non-Cartesian magnetic resonance imaging and reconstruct both a numerical phantom and an in vivo cardiac image. Index Terms--Discrete Fourier transforms, magnetic resonance imaging (MRI), parallel algorithms, parallel architectures.