Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware

Area of Science:

• Computer Science
• Medical Imaging
• Signal Processing

Background:

• The nonequispaced fast Fourier transform (NFFT) is crucial for reconstructing images from non-Cartesian data in medical imaging.
• The convolution step in NFFT has historically been computationally intensive, limiting reconstruction speed.
• Graphics Processing Units (GPUs) offer parallel processing capabilities that can accelerate such computations.

Purpose of the Study:

• To develop and evaluate a fast parallel algorithm for the nonequispaced fast Fourier transform (NFFT) utilizing commodity graphics hardware (GPU).
• To specifically optimize the convolution step within the NFFT, addressing its previous performance bottleneck.
• To demonstrate the algorithm's applicability and performance in medical imaging, particularly for non-Cartesian magnetic resonance imaging (MRI).

Main Methods:

• A novel parallel algorithm for NFFT was implemented on GPU hardware.
• The convolution step was re-engineered for GPU acceleration.
• Performance was assessed using radial and spiral trajectories and various convolution kernels.
• Accuracy was quantitatively evaluated across different settings.
• The algorithm was applied to reconstruct a numerical phantom and an in vivo cardiac MRI dataset.

Main Results:

• The GPU-accelerated NFFT convolution achieved speedups of up to 85 times compared to the open-source NFFT library on a high-performance CPU.
• Performance was analyzed for different sampling distributions (radial, spiral) and convolution kernels.
• The accuracy of the GPU implementation was validated.
• Successful reconstruction of non-Cartesian MRI data, including a numerical phantom and a cardiac image, was demonstrated.

Conclusions:

• The proposed GPU-based NFFT algorithm offers a significant speed improvement for non-Cartesian MRI reconstruction.
• This acceleration is primarily driven by the optimized GPU convolution implementation.
• The method is accurate and applicable to real-world medical imaging scenarios, enhancing the efficiency of gridding techniques.