Application of GPU processing for acceleration of the non-uniform discrete Fourier transform

Kai Zhuang, Daniel O. Trad

We implemented a non-uniform discrete Fourier transform(NUDFT) algorithm in C++ on both CPU and GPU. In this paper, we explore the advantages and challenges of the implementation of the CUDA API on the non-uniform discrete Fourier transform. The implementation of CUDA is interesting in this application because the non-uniform transform is very time-consuming on the CPU due to O(n²) complexity and the high amounts of memory operations that are performed due to the non-uniform natures of the transform.We implement the NUDFT in CUDA to see if the superior multi-threading performance of GPUs can offset the losses due to memory operations, to make NUDFT and in extension interpolation via NUDFT a computationally viable alternative.