Today : Wed, Aug 22 2018 .

Fast Multipole Methods (CTP)

Software Packages and Websites:

  • NUFFT: Non-Uniform FFT software by L. Greengard and J. Y. Lee.
  • NFFT: NFFT package developed at the Chemnitz University of Technology and the University of Lübeck.
  • NUFFT: NUFFT package developed at the University of Michigan.


  • Dutt, A.; Rokhlin, V. Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14 (1993), no. 6, 1368--1393.
  • Dutt, A.; Rokhlin, V. Fast Fourier transforms for nonequispaced data. II. Appl. Comput. Harmon. Anal. 2 (1995), no. 1, 85--100.
  • Greengard, Leslie; Lee, June-Yub Accelerating the nonuniform fast Fourier transform. SIAM Rev. 46 (2004), no. 3, 443--454 (*)
  • Lee, June-Yub; Greengard, Leslie The type 3 nonuniform FFT and its applications. J. Comput. Phys. 206 (2005), no. 1, 1--5.
  • Fessler, J.A.; Sutton, B.P., Nonuniform fast Fourier transforms using min-max interpolation Signal Processing, IEEE Transactions on Acoustics, Speech, and Signal Processing, Volume 51, Issue 2, Feb. 2003 Page(s):560 - 574
  • Keiner, J., Kunis, S., and Potts, D. Using NFFT 3 - a software library for various nonequispaced fast Fourier transforms ACM Trans. Math. Software, accepted.
  • Potts, D. and Steidl, G. Fast summation at nonequispaced knots by NFFTs. SIAM J. Sci. Comput. 24, 2013-2037.
  • S. Kunis and D. Potts, Stability Results for Scattered Data Interpolation by Trigonometric Polynomials, SIAM J. Sci. Comput. 29, 1403 - 1419.
  • S. Kunis and D. Potts, Time and memory requirements of the Nonequispaced FFT , Sampling Theory in Signal and Image Processing 7, 77 - 100,

This site has been visited 9643 times. Page: Main.T-NuFFT - Last Modified : Fri, May 22 2009

NSF-National Science Foundation DOE-US Dept of Energy

Maintained by Jun Jia, Bo Zhang, and Jingfang Huang
Copyright 2008