Time and Memory Requirements of the Nonequispaced FFT

被引：1
作者：
Stefan Kunis
Daniel Potts
机构：
[1] Chemnitz University of Technology,Department of Mathematics
来源：
Sampling Theory in Signal and Image Processing | 2008年 / 7卷 / 1期
关键词：
Nonequispaced Fast Fourier Transform; FFT; 65T50; 65F50;
D O I：
10.1007/BF03549487
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：77 / 100
页数：23
相关论文
共 71 条
[1]  
Anderson C(1996)Rapid computation of the discrete Fourier transform, SIAM J. Sci. Comput. 17 913-919
[2]  
Dahleh M(2006)Fast and accurate polar Fourier transform Appl. Comput. Harmon. Anal. 21 145-167
[3]  
Averbuch A(2005)Rapid gridding reconstruction with a minimal oversampling ratio, IEEE Trans. Med. Imag. 24 799-808
[4]  
Coifman R(1995)On the fast Fourier transform of functions with singularities Appl. Comput. Harmon. Anal. 2 363-381
[5]  
Donoho D L(2006)Fast discrete curvelet transforms, SIAM Multiscale Model. Simul. 3 861-899
[6]  
Elad M(1999)Nonuniform fast Fourier transform Geophysics 64 539-551
[7]  
Israeli M(1993)Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Stat. Comput. 14 1368-1393
[8]  
Beatty P J(1995)Fast Fourier transforms for nonequispaced data II Appl. Comput. Harmon. Anal. 2 85-100
[9]  
Nishimura D G(2007)Field inhomogeneity correction based on gridding reconstruction, IEEE Trans. Med. Imag. 26 374-384
[10]  
Pauly J M(1995)Efficient numerical methods in non-uniform sampling theory Numer. Math. 69 423-440
12345678