A parallel hierarchical tensor product method for n-dimensional interpolation in the Fourier domain
- 27 November 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
Abstract
Parallel multi-dimensional interpolation in the complex Fourier domain (also known as the non-uniform fast Fourier transform) encounters major challenges, due to computation issues such as increasing computation complexity and space complexity. For instance, the contemporary graphics processing unit (GPU) is limited by the relatively small memory size and the increasing size of the interpolator. This issue makes multidimensional Fourier domain interpolation problematic, while finding an optimized configuration remains an unsolved challenge in industrial applications, e.g. magnetic resonance imaging (MRI) or computerized tomography. To enhance the performance of multi-dimensional interpolation on GPU, a new parallel hierarchical tensor products tree approach is proposed. The method combines the composite 1D interpolators under the limitation imposed by the memory size of the device. The resultant run-time performance on the GPU varies with different configurations. The best-tuned method is 2.52-4.98× faster than the compressed sparse row (CSR) on the discrete GPU and 4.16-9.59× faster than CSR on the integrated GPU. The hierarchical tensor product interpolation is used to compute the multi-dimensional nonuniform fast Fourier transform. An acceleration of 30× was achieved in 3D MRI reconstruction.Keywords
This publication has 26 references indexed in Scilit:
- Interpolation of GPS and Geological Data Using InSAR Deformation Maps: Method and Application to Land Subsidence in the Alto Guadalentín Aquifer (SE Spain)Remote Sensing, 2016
- Implementation of Cubic Spline Interpolation on Parallel Skeleton Using Pipeline Model on CPU-GPU Cluster2016
- Impact of data layouts on the efficiency of GPU-accelerated IDW interpolationSpringerPlus, 2016
- PyCUDA and PyOpenCL: A scripting-based approach to GPU run-time code generationParallel Computing, 2012
- Improving the visualization of electron-microscopy data through optical flow interpolation2011
- Implementing sparse matrix-vector multiplication on throughput-oriented processors2009
- Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier TransformsACM Transactions on Mathematical Software, 2009
- Lagrange interpolation on subgrids of tensor product gridsMathematics of Computation, 2003
- Nonuniform fast fourier transforms using min-max interpolationIEEE Transactions on Signal Processing, 2003
- Spline-surface interpolation, spatial filtering, and trend surfaces for geological mapped variablesMathematical Geology, 1973