Kunis, Stefan ; Potts, Daniel : Time and memory requirements of the Nonequispaced FFT

Author(s):

Kunis, Stefan
Potts, Daniel

Title:

Time and memory requirements of the Nonequispaced FFT

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 1, 2006

Mathematics Subject Classification:

65T50			[ Discrete and fast Fourier transforms ]
42C10			[ Fourier series in special orthogonal functions ]
15A23			[ Factorization of matrices ]

Abstract:

We consider the fast Fourier transform at nonequispaced nodes (NFFT) and give detailed information on the time and memory requirements of its building blocks. This manuscript reviews the state of the art approaches and focuses within the most successful scheme on the computational most involved part. Beside a rigorous derivation of an lookup table technique, we compare a wide range of precomputation schemes which lead to substantially different computation times of the NFFT. In particular, we show how to balance accuracy, memory usage, and computation time.

Keywords:

Nonequispaced Fast Fourier Transform, NFFT

Language:

English

Publication time:

3 / 2006