text: This paper reports the development of a Python Non-Uniform Fast Fourier Transform (PyNUFFT) package, which accelerates non-Cartesian image reconstruction on heterogeneous platforms. Scientific computing with Python encompasses a mature and integrated environment. The NUFFT algorithm has been extensively used for non-Cartesian image reconstruction but previously there was no native Python NUFFT library. The current PyNUFFT software enables multi-dimensional NUFFT on heterogeneous platforms. The PyNUFFT also provides several solvers, including the conjugate gradient method, @math 1 total-variation regularized ordinary least square (L1TV-OLS) and @math 1 total-variation regularized least absolute deviation (L1TV-LAD). Metaprogramming libraries were employed to accelerate PyNUFFT. The PyNUFFT package has been tested on multi-core CPU and GPU, with acceleration factors of 6.3 - 9.5 @math on a 32 thread CPU platform and 5.4 - 13 @math on the GPU.
  @cite_30: Radially encoded MRI has gained increasing attention due to its motion insensitivity and reduced artifacts. However, because its samples are collected nonuniformly in the k-space, multidimensional (especially 3-D) radially sampled MRI image reconstruction is challenging. The objective of this paper is to develop a reconstruction technique in high dimensions with on-the-fly kernel calculation. It implements general multidimensional nonuniform fast Fourier transform (NUFFT) algorithms and incorporates them into a k-space image reconstruction framework. The method is then applied to reconstruct from the radially encoded k-space data, although the method is applicable to any non-Cartesian patterns. Performance comparisons are made against the conventional Kaiser-Bessel (KB) gridding method for 2-D and 3-D radially encoded computer-simulated phantoms and physically scanned phantoms. The results show that the NUFFT reconstruction method has better accuracy-efficiency tradeoff than the KB gridding method when the kernel weights are calculated on the fly. It is found that for a particular conventional kernel function, using its corresponding deapodization function as a scaling factor in the NUFFT framework has the potential to improve accuracy. In particular, when a cosine scaling factor is used, the NUFFT method is faster than KB gridding method since a closed-form solution is available and is less computationally expensive than the KB kernel (KB griding requires computation of Bessel functions). The NUFFT method has been successfully applied to 2-D and 3-D in vivo studies on small animals.
  @cite_8: 
  @cite_3: The nonequispaced Fourier transform arises in a variety of application areas, from medical imaging to radio astronomy to the numerical solution of partial differential equations. In a typical problem, one is given an irregular sampling of N data in the frequency domain and one is interested in reconstructing the corresponding function in the physical domain. When the sampling is uniform, the fast Fourier transform (FFT) allows this calculation to be computed in O(N log N ) operations rather than O(N 2 ) operations. Unfortunately, when the sampling is nonuniform, the FFT does not apply. Over the last few years, a number of algorithms have been developed to overcome this limitation and are often referred to as nonuniform FFTs (NUFFTs). These rely on a mixture of interpolation and the judicious use of the FFT on an oversampled grid (A. Dutt and V. Rokhlin, SIAM J. Sci. Comput., 14 (1993), pp. 1368-1383). In this paper, we observe that one of the standard interpolation or "gridding" schemes, based on Gaussians, can be accelerated by a significant factor without precomputation and storage of the interpolation weights. This is of particular value in two- and three- dimensional settings, saving either 10 d N in storage in d dimensions or a factor of about 5-10 in CPUtime (independent of dimension).
  @cite_24: The fast Fourier transform (FFT) is used widely in signal processing for efficient computation of the FT of finite-length signals over a set of uniformly spaced frequency locations. However, in many applications, one requires nonuniform sampling in the frequency domain, i.e., a nonuniform FT. Several papers have described fast approximations for the nonuniform FT based on interpolating an oversampled FFT. This paper presents an interpolation method for the nonuniform FT that is optimal in the min-max sense of minimizing the worst-case approximation error over all signals of unit norm. The proposed method easily generalizes to multidimensional signals. Numerical results show that the min-max approach provides substantially lower approximation errors than conventional interpolation methods. The min-max criterion is also useful for optimizing the parameters of interpolation kernels such as the Kaiser-Bessel function.
  @cite_19: Several recent methods have been proposed to obtain significant speed-ups in MRI image reconstruction by leveraging the computational power of GPUs. Previously, we implemented a GPU-based image reconstruction technique called the Illinois Massively Parallel Acquisition Toolkit for Image reconstruction with ENhanced Throughput in MRI (IMPATIENT MRI) for reconstructing data collected along arbitrary 3D trajectories. In this paper, we improve IMPATIENT by removing computational bottlenecks by using a gridding approach to accelerate the computation of various data structures needed by the previous routine. Further, we enhance the routine with capabilities for off-resonance correction and multi-sensor parallel imaging reconstruction. Through implementation of optimized gridding into our iterative reconstruction scheme, speed-ups of more than a factor of 200 are provided in the improved GPU implementation compared to the previous accelerated GPU code.
  @cite_23: We develop a new algorithm for the fast computation of discrete sums @math (j =1, . . ., M) based on the recently developed fast Fourier transform (FFT) at nonequispaced knots. Our algorithm, in particular our regularization procedure, is simply structured and can be easily adapted to different kernels K. Our method utilizes the widely known FFT and can consequently incorporate advanced FFT implementations. In summary, it requires @math arithmetic operations. We prove error estimates to obtain clues about the choice of the involved parameters and present numerical examples in one and two dimensions.
  @cite_31: 
  @cite_10: 
  @cite_11: NFFT 3 is a software library that implements the nonequispaced fast Fourier transform (NFFT) and a number of related algorithms, for example, nonequispaced fast Fourier transforms on the sphere and iterative schemes for inversion. This article provides a survey on the mathematical concepts behind the NFFT and its variants, as well as a general guideline for using the library. Numerical examples for a number of applications are given.
summary: Different kernel functions (interpolators) are available in previous NUFFT implementations, including: (1)the min-max interpoaltor @cite_24 , (2) the fast radial basis functions @cite_23 @cite_11 , (3)least square interpolator @cite_30 , (4)least mean-square error interpolato @cite_8 , (5) fast Gaussian summation @cite_3 , (6) Kaiser-Bessel function @cite_19 , (7) linear system transfer function or inverse reconstruction @cite_31 @cite_10 .