A parallel hierarchical tensor product method for n-dimensional interpolation in the Fourier domain

Hsin Chia Chen, Hao Chiao Yang, Yu Chieh Chao, Julian Nicholls, Jyh Miin Lin, Chih Ching Chen, Wei Hsuan Yu, Feng Nan Hwang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationICECIE 2021 - 2021 International Conference on Electrical, Control and Instrumentation Engineering, Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781665449663
DOIs
StatePublished - 2021
Event3rd IEEE International Conference on Electrical, Control and Instrumentation engineering, ICECIE 2021 - Kuala Lumpur, Malaysia
Duration: 27 Nov 202128 Nov 2021

Publication series

NameICECIE 2021 - 2021 International Conference on Electrical, Control and Instrumentation Engineering, Conference Proceedings

Conference

Conference3rd IEEE International Conference on Electrical, Control and Instrumentation engineering, ICECIE 2021
Country/TerritoryMalaysia
CityKuala Lumpur
Period27/11/2128/11/21

Keywords

  • hierarchical tensor product
  • interpolation
  • nonuniform
  • parallel computing

Fingerprint

Dive into the research topics of 'A parallel hierarchical tensor product method for n-dimensional interpolation in the Fourier domain'. Together they form a unique fingerprint.

Cite this