1. Introduction

Fast Fourier transforms (FFTs) are one of the “10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century” [1]. This is because the FFT is applied in almost every area of modern science, including fields as diverse as acoustics, astronomy, computational biology, fluid dynamics, medicine, physics, and digital signal processing. For example, FFTs are the basic algorithm for compression algorithms used in MP3 data generation, for digital television and radio encoding, and for digital spectrum analysis. Therefore, it is generally accepted that “the fast Fourier transform is one of the truly great computational developments of this century. It has changed the face of science and engineering so much … that it is not an exaggeration to say that life as we know it would be very different without the FFT” [2].

The classical Cooley-Tukey algorithm [3] computes the discrete Fourier transform for N, given complex coefficients in N log N floating point operations instead of N² floating point operations. It was later discovered that this algorithm was known to Carl Friedrich Gauss as early as 1805, and was subsequently rediscovered several times. Currently, the FFTW [4] package is the FFT library of choice for most applications; it is available as free software.

A severe shortcoming of traditional schemes in recent applications is that they require equispaced sampling. During the last two decades, that problem has attracted much attention. The nonequispaced fast Fourier transform (NFFT) [5] overcomes this disadvantage while keeping the number of floating point operations at N log N. NFFTs are based on the concept of trading exactness for efficiency. Instead of precise computations (up to machine precision for actual implementations), the proposed methods guarantee a user-specified target accuracy.

New applications that utilize the NFFT continue to arise, such as 3D imaging. Several research groups have applied nonequidistant FFTs to applications in geoscience, crystallography, or computational biology for the computation of protein interactions, or for reconstruction in electron microscopy. In each of these applications, the NFFT is the computationally dominant task; one has to deal with different requirements with respect to the target accuracy, the usage of memory, and the actual computation time [6].

2. Background of the NFFT

An early review of several algorithms [7,8] has been given by Ware [9]. Steidl [10] obtained a unified approach to fast algorithms for the NFFT. The main idea is the use of a window function that is well localized in space, as well as in the frequency domain. Then, one can use an approximation obtained by translations of the scaled window function to estimate the approximation error [11]. It became clear that this approach was related to the gridding algorithm, which was known years earlier in the context of image processing and astrophysics. A widely used implementation is now available as part of the NFFT package [5], and is based on the FFTW [4]. If you wish to cite NFFT, the most current general paper is by Keiner et al. [12].

Some important applications of the NFFT follow.

3. Applications

Nonequispaced sampling

The nonequispaced or irregular sampling problem is concerned with recovery of a band-limited signal from a sequence of samples that might be taken in an irregular way. From the linear algebra viewpoint, one has to “invert” the NFFT. Hence, one has to solve a least squares or an interpolation problem. An efficient scheme for the first problem is known as the ACT method (adaptive weights method, conjugate gradient acceleration, and Toeplitz matrices) [13], suggested by Feichtinger, Groechenig, and Strohmer. Kunis has developed an efficient scheme for the second problem [6].

Nonequispaced convolution

Another application is the so-called nonequispaced convolution. For lattices, the discrete convolution and its fast computation are typically realized by fast Fourier transforms exploiting the basic property e^i(y−x) = e^{2 iy} e^-2ix. Along these lines, the convolution at nonequispaced knots should be computed by Fourier methods as well, more precisely by the NFFT. This new method includes the fast Gauss transform or the convolution with kernels of the form 1/x, which have been often realized with the fast multipole method (FMM). In summary, the advantage of the NFFT, which has almost the same arithmetic complexity as the FMM, is its simple structure, which resembles ideas from the fast convolution by FFTs and allows an immediate incorporation of various kernels [5].

Further algorithms based on the NFFT

In recent years, it has become clear that the NFFT is a building block for more algorithms (see Figure 1). One important generalization replaces the system of complex exponentials with other systems of functions. In particular, the spherical analogue of the usual Fourier basis functions, the standard orthonormal spherical harmonics, plays a fundamental role. Therefore, the development of a fast spherical Fourier transform by Driscoll and Healy [14] was a breakthrough. A variety of authors have improved this algorithm, and it has been shown that one can compute with spherical harmonics efficiently. In order to overcome the main drawback that all previous spherical Fourier transforms had in relying on a specific grid, a combination with the NFFT has been developed. The nonequispaced fast spherical Fourier transform and its inverse for solving the irregular sampling problem on the sphere are part of the NFFT package [5]. There are further algorithms based on the NFFT, such as the curvelet transform, the ridgelet transform, the shearlet transform, and the polar FFT, with a wide range of applications in image processing (see the related Web pages section).

4. Software Packages

Currently, the NFFT package [5] is the most widespread library for generalized FFTs. The tremendous computing power of next-generation supercomputers like Blue Gene/Q mainly arises from massive parallelism. Therefore, one has to consider appropriate algorithmic reformulations of the NFFT, that is, the NFFT must be split into multiple subproblems that can be computed concurrently. Such parallel NFFT algorithms have been recently developed and implemented for shared memory architectures [15], distributed memory architectures [16,17], and graphic cards [18]. With the help of these parallel NFFT modules, the porting of existing serial applications to parallel platforms becomes straightforward. For high-dimensional problems, the hyperbolic cross FFT [19] was developed.

Created: May 08 2008 Last updated: Apr 09 2013