SIAM News Blog
SIAM News

# Next Generation FFT Algorithms in Theory and Practice: Parallel Implementations, Sparse FFTs, and Applications

A two-part minisymposium at the 2019 SIAM Conference on Computational Science and Engineering, which took place earlier this year in Spokane, Wash., focused on the fast Fourier transform (FFT), an algorithm that is used in a wide variety of applications yet does not make optimal use of many current hardware platforms. This minisymposium encouraged the exchange of information between researchers working on alternative FFT algorithms—such as sparse and non-uniform FFTs—with those working on FFT implementations, particularly for parallel hardware.

The 2019 SIAM Conference on Computational Science and Engineering, which took place earlier this year in Spokane, Wash., featured a two-part minisymposium entitled "Next Generation FFT Algorithms in Theory and Practice: Parallel Implementations, Sparse FFTs, and Applications."
Daisuke Takahashi (University of Tsukuba) organized the minisymposium. After briefly discussing its role in helping to collect different viewpoints and form a community, he opened the first session by showing the results of a parallel three-dimensional real FFT’s implementation with two-dimensional decomposition; this appeared efficient in terms of improving the performance of Intel Xeon Phi clusters.

Mark Iwen (Michigan State University) then gave an interesting talk about sparse Fourier transforms (SFTs), generalizations, and extensions. He and his graduate students have considered SFT algorithms for approximate computation of the best $$s$$-term (i.e., a best possible sparse approximation) for the approximation of the discrete Fourier transform (DFT) via compressive sensing theorems. Iwen showed experimental results of DMSFT-4, which is faster than FFTW and MIT 2.0 libraries in terms of computing sparsity. More details are available in [3].

Sina Bittens (University of Göttingen) continued with a presentation about the implementation of sparse FFT with structured sparsity. She demonstrated how to use any extra structure that exists in a vector’s DFT to obtain additional computational gains. Bittens used a generalized algorithm in the form of Iwen’s sparse algorithm and a new decomposition idea to provide an example of the algorithm’s function. This method achieves a runtime that is sublinear in input length and scales sub-quadratically in sparsity. It guarantees the same type of error as many compressive sensing methods.

Samar Aseeri (King Abdullah University of Science and Technology (KAUST)) began the second session by briefing the audience on efforts achieved thus far with regard to the FFT project in the Exascale era. She also spoke about how this meeting—together with other meetings—revives the Arden workshop [2] that took place two years after publication of the FFT algorithm [1]. Aseeri highlighted ongoing work with collaborators at the Indian Institute of Technology Kanpur to speed up the FFT by utilizing the full bandwidth offered by KAUST’s Cray XC40 machine.

Bosu Choi, (University of Texas at Austin) continued with a presentation about her work with high-dimensional sparse FFTs. She had to use partial unwrapping and tilting approaches to allow efficient computing of the SFTs in order to implement her extended high-dimensional sparse FFT algorithm for large dimensions. Choi gave a detailed description of the method and numerical experiments, addressing samples both with and without noise.

From left to right: Bosu Choi (University of Texas at Austin), Toni Volkmer (Chemnitz University of Technology), Sina Bittens (University of Goettingen), Mark Iwen (Michigan State University), Mark Carpenter (NASA), Samar Aseeri (King Abdullah University of Science and Technology), Daisuke Takahashi (University of Tsukuba), and Henry A. Boateng (Bates College).

Toni Volkmer (Chemnitz University of Technology) next delivered a presentation entitled “Rank-1 Lattice Based High-dimensional Approximation and Sparse FFT.” Volkmer uses a special spatial discretization called multiple rank-1 lattice. He talked about the approximation of multivariate periodic functions by trigonometric polynomials based on one-dimensional FFTs, then discussed two cases with corresponding numerical results. The first case assumed that the locations of the nonzero (or approximately largest) Fourier coefficients are known while the second—where researchers use a sparse FFT method based on dimension-incremental projections for frequency detection—assumed the opposite. Volkmer offered numerical results for up to 25 spatial dimensions for the first case and 10 spatial dimensions for the second.

Finally, Henry A. Boateng (Bates College), presented his work, titled “A Periodic Treecode Method for Electrostatics in Molecular Dynamics Simulations.” He demonstrated aspects of molecular dynamics (MD) simulations for the FFT audience, then showed how researchers use FFT in some terms to gain an O(nlogn) complexity for quick calculations in problems associated with MD simulations. Boateng also provided a brief description of his ongoing work dealing with the periodic tree-code.

References
[1] Cooley, J.W., & Tukey, J.W. (1965). An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comp., 19(90), 297-301.
[2] Cooley, J., Garwin, R., Rader, C., Bogert, B., & Stockham, T. (1969).The 1968 Arden House Workshop of Fast Fourier Transform Processing.” IEEE Trans. Audio Electroacoust., 17(2), 66-75.
[3] Merhi, S., Zhang, R., Iwen, M.A., & Christlieb, A. (2018). A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees. J. Fourier Anal. Appl., 1-34.

Samar Aseeri is a computational scientist at King Abdullah University of Science and Technology in Saudi Arabia.