Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier Transforms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier Transforms

Full text

Pdf (1.05 MB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 36 , Issue 4 (August 2009) table of contents

Article No. 19

Year of Publication: 2009

ISSN:0098-3500

Authors

Jens Keiner	University of Lübeck
Stefan Kunis	Chemnitz University of Technology
Daniel Potts	Chemnitz University of Technology

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 79, Downloads (12 Months): 194, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1555386.1555388 What is a DOI?

ABSTRACT

NFFT 3 is a software library that implements the nonequispaced fast Fourier transform (NFFT) and a number of related algorithms, for example, nonequispaced fast Fourier transforms on the sphere and iterative schemes for inversion. This article provides a survey on the mathematical concepts behind the NFFT and its variants, as well as a general guideline for using the library. Numerical examples for a number of applications are given.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Abramowitz, M. and Stegun, I. A., Eds. 1972. Handbook of Mathematical Functions. National Bureau of Standards, Washington, DC.
	2	Anderson, C. and Dahleh, M. 1996. Rapid computation of the discrete Fourier transform. SIAM J. Sci. Comput. 17, 913--919.
	3	Andersson, F. and Beylkin, G. 2005. The fast Gauss transform with complex parameters. J. Comput. Phys. 203, 274--286.
	4	Averbuch, A., Coifman, R., Donoho, D. L., Elad, M., and Israeli, M. 2006. Fast and accurate polar Fourier transform. Appl. Comput. Harmon. Anal. 21, 145--167.
	5	Bass, R. F. and Gröchenig, K. 2004. Random sampling of multivariate trigonometric polynomials. SIAM J. Math. Anal. 36, 773--795.
	6	Beatson, R. K. and Greengard, L. 1997. A short course on fast multipole methods. In Wavelets, Multilevel Methods and Elliptic PDEs, M. Ainsworth, J. Levesley, W. A. Light, and M. Marletta, Eds. Clarendon Press, Oxford, U.K., 1--37.
	7	Beatty, P. J., Nishimura, D. G., and Pauly, J. M. 2005. Rapid gridding reconstruction with a minimal oversampling ratio. IEEE Trans. Med. Imag. 24, 799--808.
	8	Beylkin, G. 1995. On the fast Fourier transform of functions with singularities. Appl. Comput. Harmon. Anal. 2, 363--381.
	9	Beylkin, G., Kurcz, C., and Monzón, L. 2007. Grids and transforms for band-limited functions in a disk. Inverse Prob. 23, 2059--2088.
	10	Björck, Å. 1996. Numerical Methods for Least Squares Problems. SIAM, Philadelphia, PA.
	11	Bungartz, H.-J. and Griebel, M. 2004. Sparse grids. Acta Numer. 13, 147--269.
	12	Candes, E. J., Demanet, L., Donoho, D. L., and Ying, L. 2006. Fast discrete curvelet transforms. SIAM Multiscale Model. Simul. 3, 861--899.
	13	Cooley, J. W. and Tukey, J. W. 1965. An algorithm for machine calculation of complex Fourier series. Math. Comput. 19, 297--301.
	14	Donoho, D., Maleki, A., and Shaharam, M. 2006. Wavelab 850. http://www-stat.stanford.edu/~wavelab.
	15	Driscoll, J. R. and Healy, D. 1994. Computing Fourier transforms and convolutions on the 2--sphere. Adv. Appl. Math. 15, 202--250.
	16	Driscoll, J. R., Healy, D., and Rockmore, D. 1996. Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. 26, 1066--1099.
	17	Duijndam, A. J. W. and Schonewille, M. A. 1999. Nonuniform fast Fourier transform. Geophys. 64, 539--551.
	18	Dutt, A. and Rokhlin, V. 1993. Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Stat. Comput. 14, 1368--1393.
	19	Dutt, A. and Rokhlin, V. 1995. Fast Fourier transforms for nonequispaced data II. Appl. Comput. Harmon. Anal. 2, 85--100.
	20	Eggers, H., Knopp, T., and Potts, D. 2007. Field inhomogeneity correction based on gridding reconstruction. IEEE Trans. Med. Imag. 26, 374--384.
	21	Elbel, B. and Steidl, G. 1998. Fast Fourier transform for nonequispaced data. In Approximation Theory IX, C. K. Chui and L. L. Schumaker, Eds. Vanderbilt University Press, Nashville, TN, 39--46.
	22	Feichtinger, H. G., Gröchenig, K., and Strohmer, T. 1995. Efficient numerical methods in non-uniform sampling theory. Numer. Math. 69, 423--440.
	23	Fenn, M., Kunis, S., and Potts, D. 2006. Fast evaluation of trigonometric polynomials from hyperbolic crosses. Numer. Algorith. 41, 339--352.
	24	Fenn, M., Kunis, S., and Potts, D. 2007. On the computation of the polar FFT. Appl. Comput. Harmon. Anal. 22, 257--263.
	25	Fenn, M. and Potts, D. 2005. Fast summation based on fast trigonometric transforms at nonequispaced nodes. Numer. Lin. Algebr. Appl. 12, 161--169.
	26	Fenn, M. and Steidl, G. 2004. Fast NFFT based summation of radial functions. Sampl. Theor. Signal Image Process. 3, 1--28.
	27	Fessler, J. A. and Sutton, B. P. 2002. NUFFT---nonuniform FFT toolbox for Matlab. http://www.eecs.umich.edu/~fessler/code.
	28	Fessler, J. A. and Sutton, B. P. 2003. Nonuniform fast Fourier transforms using min-max interpolation. IEEE Trans. Signal Process. 51, 560--574.
	29	Fourmont, K. 2003. Nonequispaced fast Fourier transforms with applications to tomography. J. Fourier Anal. Appl. 9, 431--450.
	30	Frigo, M. and Johnson, S. G. 2005a. The design and implementation of FFTW3. Proc. IEEE 93, 216--231.
	31	Frigo, M. and Johnson, S. G. 2005b. FFTW, C subroutine library. http://www.fftw.org.
	32	Greengard, L. and Lee, J.-Y. 2004. Accelerating the nonuniform fast Fourier transform. SIAM Rev. 46, 443--454.
	33	Jackson, J. I., Meyer, C. H., Nishimura, D. G., and Macovski, A. 1991. Selection of a convolution function for Fourier inversion using gridding. IEEE Trans. Med. Imag. 10, 473--478.
	34	Keiner, J., Kunis, S., and Potts, D. 2006a. Fast summation of radial functions on the sphere. Computing 78, 1--15.
	35	Keiner, J., Kunis, S., and Potts, D. 2006b. NFFT 3.0, C subroutine library. http://www.tu-chemnitz.de/~potts/nfft.
	36	Keiner, J., Kunis, S., and Potts, D. 2007. Efficient reconstruction of functions on the sphere from scattered data. J. Fourier Anal. Appl. 13, 435--458.
	37	Keiner, J. and Potts, D. 2008. Fast evaluation of quadrature formulae on the sphere. Math. Comput. 77, 397--419.
	38	Knopp, T., Kunis, S., and Potts, D. 2007. A note on the iterative MRI reconstruction from nonuniform k-space data. Int. J. Biomed. Imag. ID 24727.
	39	Kunis, S. 2008. Nonequispaced fast Fourier transforms without oversampling. Proc. Appl. Math. Mech. 8, 10977--10978.
	40	Kunis, S. and Potts, D. 2003. Fast spherical Fourier algorithms. J. Comput. Appl. Math. 161, 75--98.
	41	Kunis, S. and Potts, D. 2007. Stability results for scattered data interpolation by trigonometric polynomials. SIAM J. Sci. Comput. 29, 1403--1419.
	42	Kunis, S. and Potts, D. 2008. Time and memory requirements of the nonequispaced FFT. Sampl. Theor. Signal Image Process. 7, 77--100.
	43	Kunis, S., Potts, D., and Steidl, G. 2006. Fast Gauss transform with complex parameters using NFFTs. J. Numer. Math. 14, 295--303.
	44	Lee, J.-Y. and Greengard, L. 2005. The type 3 nonuniform FFT and its applications. J. Comput. Phys. 206, 1--5.
	45	Ma, J. and Fenn, M. 2006. Combined complex ridgelet shrinkage and total variation minimization. SIAM J. Sci. Comput. 28, 984--1000.
	46	National Aeronautics and Space Administration. 2007. NASA AIRS Homepage. http://disc.gsfc.nasa.gov/AIRS/index.shtml.
	47	Nguyen, N. and Liu, Q. H. 1999. The regular Fourier matrices and nonuniform fast Fourier transforms. SIAM J. Sci. Comput. 21, 283--293.
	48	Nieslony, A. and Steidl, G. 2003. Approximate factorizations of Fourier matrices with nonequispaced knots. Lin. Algebr. Appl. 266, 337--351.
	49	Pelt, J. 1997. Fast computation of trigonometric sums with applications to frequency analysis of astronomical data. In Astronomical Time Series, D. Maoz, A. Sternberg, and E. Leibowitz, Eds. Kluwer, Dordrecht, The Netherlands, 179--182.
	50	Pöplau, G., Potts, D., and van Rienen, U. 2006. Calculation of 3D space-charge fields of bunches of charged particles by fast summation. In Scientific Computing in Electrical Engineering, A. Anile, G. Alì, and G. Mascaly, Eds. Springer, Berlin, Germany, 241--246.
	51	Potts, D. 2003a. Fast algorithms for discrete polynomial transforms on arbitrary grids. Lin. Algebr. Appl. 366, 353--370.
	52	Potts, D. 2003b. Schnelle Fourier-Transformationen für nichtäquidistante Daten und Anwendungen. Habilitation, Universität zu Lübeck. http://www.tu-chemnitz.de/~potts.
	53	Potts, D. and Steidl, G. 2000. New Fourier reconstruction algorithms for computerized tomography. In Proceedings of SPIE: Wavelet Applications in Signal and Image Processing VIII, A. Aldroubi, A. Laine, and M. Unser, Eds. Lecture Notes in Computer Science, Vol. 4119. Springer, Berlin, Germany, 13--23.
	54	Potts, D. and Steidl, G. 2001. A new linogram algorithm for computerized tomography. IMA J. Numer. Anal. 21, 769--782.
	55	Potts, D. and Steidl, G. 2002. Fourier reconstruction of functions from their nonstandard sampled Radon transform. J. Fourier Anal. Appl. 8, 513--533.
	56	Potts, D. and Steidl, G. 2003. Fast summation at nonequispaced knots by NFFTs. SIAM J. Sci. Comput. 24, 2013--2037.
	57	Potts, D., Steidl, G., and Nieslony, A. 2004. Fast convolution with radial kernels at nonequispaced knots. Numer. Math. 98, 329--351.
	58	Potts, D., Steidl, G., and Tasche, M. 1998. Fast algorithms for discrete polynomial transforms. Math. Comput. 67, 1577--1590.
	59	Potts, D., Steidl, G., and Tasche, M. 2001. Fast Fourier transforms for nonequispaced data: A tutorial. In Modern Sampling Theory: Mathematics and Applications, J. J. Benedetto and P. J. S. G. Ferreira, Eds. Birkhäuser, Boston, MA, 247--270.
	60	Rokhlin, V. and Tygert, M. 2006. Fast algorithms for spherical harmonic Expansions. SIAM J. Sci. Comput. 27, 1903--1928.
	61	Sorensen, T. S., Schaeffter, T., No, K. O., and Hansen, M. S. 2008. Accelerating the nonequispaced fast Fourier transform on commodity graphics hardware. IEEE Trans. Med. Imag. 27, 538--547.
	62	Sprengel, F. 2000. A class of function spaces and interpolation on sparse grids. Numer. Funct. Anal. Optim. 21, 273--293.
	63	Sramek, R. A. and Schwab, F. R. 1989. Imaging. In Synthesis Imaging in Radio Astronomy: A Collection of Lectures from the Third NRAO Synthesis Imaging Summer School, R. Perley, F. R. Schwab, and A. Bridle, Eds. Astronomical Society of the Pacific, San Francisco, CA, 83--138.
	64	Steidl, G. 1998. A note on fast Fourier transforms for nonequispaced grids. Adv. Comput. Math. 9, 337--353.
	65	Suda, R. and Takami, M. 2002. A fast spherical harmonics transform algorithm. Math. Comput. 71, 703--715.
	66	Sutton, B. P., Noll, D. C., and Fessler, J. A. 2003. Fast, iterative, field-corrected image reconstruction for MRI in the presence of field inhomogeneities. IEEE Trans. Med. Imag. 22, 178--188.
	67	Tian, B. and Liu, Q. H. 2000. Nonuniform fast cosine transform and Chebyshev PSTD algorithm. J. Electromagn. Waves Appl. 14, 797--798.
	68	Van Loan, C. F. 1992. Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia, PA.
	69	Ware, A. F. 1998. Fast approximate Fourier transforms for irregularly spaced data. SIAM Rev. 40, 838--856.
	70	Zenger, C. 1991. Sparse grids. In Parallel Algorithms for Partial Differential Equations (Kiel, 1990), W. Hackbusch, Ed. Notes Numer. Fluid Mech. 31, 241--251.