|
|
Time and memory requirements of the nonequispaced FFT.(fast Fourier transform )(Technical report)
- Article from:
-
Sampling Theory in Signal and Image Processing
- Article date:
-
January 1, 2008
- Author:
- Kunis, Stefan; Potts, Daniel
|
Copyright informationCOPYRIGHT 2008 Sampling Publishing. This material is published under license from the publisher through the Gale Group, Farmington Hills, Michigan. All inquiries regarding rights should be directed to the Gale Group. (Hide copyright information)
|
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 most computationally involved part. Beside a rigorous derivation of a 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.
Key words and phrases. Nonequispaced Fast Fourier Transform, FFT
1 Introduction
This paper ...