Wissen, was gut ist. Studieren in Chemnitz.
Kunis, Stefan; Potts, Daniel : Time and memory requirements of the Nonequispaced FFT

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