Researchers from the University of Central Florida credit ArrayFire in a paper published in IEEE Transactions on Signal Processing. The paper is titled “An Exact and Fast Computation of Discrete Fourier Transform for Polar and Spherical Grid” and provides the first exact and fast solution to the problem of obtaining discrete Fourier transform for polar and spherical grids.
This paper is fully reproducible on Github.
Summary
Numerous applied problems of two-dimensional (2-D) and 3-D imaging are formulated in the continuous domain. They emphasize obtaining and manipulating the Fourier transform in polar and spherical coordinates. However, translating continuum ideas with discretely sampled data on a Cartesian grid is problematic. There exists no exact and fast solution to the problem of obtaining discrete Fourier transform for polar and spherical grids in the literature. In this paper, we develop exact algorithms for the above problem in 2-D, and 3-D, which involve only 1-D equispaced fast Fourier transforms with no interpolation or approximation at any stage. The result of the proposed approach leads to a fast solution with very high accuracy.
The paper describes the computational procedure to obtain the solution in 2-D and 3-D, including fast forward and inverse, transforms. The researchers find the nested multilevel matrix structure of the inverse process. They propose a hybrid grid and use a preconditioned conjugate gradient method that drastically improves the condition number.
The Algorithm
The mathematical details for the algorithm are provided in the paper. The following is an example figure from the paper showing the construction of the spherical algorithm in 3-D.
The authors shared an additional link where they used Unreal Engine to create great visualizations of this work. Here is a sample of the images there.
The Results
Figure 15 from the paper shows performance benchmarks. The open source ArrayFire version is an order of magnitude faster than the CPU and the GPU versions available from a proprietary math product.
Thanks to these researchers for sharing their great work with us!