Lightweight non-uniform Fast Fourier Transform in Python
nfftpackage is a lightweight implementation of the non-equispaced fast Fourier transform (NFFT), implemented via numpy and scipy and released under the MIT license. For information about the NFFT algorithm, see the paper Using NFFT 3 – a software library for various nonequispaced fast Fourier transforms.
nfftpackage achieves comparable performance to the C package described in that paper, without any customized compiled code. Rather, it makes use of the computational building blocks available in NumPy and SciPy. For a discussion of the algorithm and this implementation, see the Implementation Walkthrough notebook.
nfftpackage implements one-dimensional versions of the forward and adjoint non-equispaced fast Fourier transforms;
The forward transform:
And the adjoint transform:
In both cases, the wavenumbers k are on a regular grid from -N/2 to N/2, while the data values x_j are irregularly spaced between -1/2 and 1/2.
The direct and fast version of these algorithms are implemented in the following functions:
nfft.ndft: direct forward non-equispaced Fourier transform
nfft.nfft: fast forward non-equispaced Fourier transform
nfft.ndft_adjoint: direct adjoint non-equispaced Fourier transform
nfft.nfft_adjoint: fast adjoint non-equispaced Fourier transform
The direct version of each transform has a computational complexity of approximately O[NM], while the NFFT has a computational complexity of approximately O[N log(N) + M log(1/ϵ)], where ϵ is the desired precision of the result. In the current implementation, memory requirements scale as approximately O[N + M log(1/ϵ)].
Another option for computing the NFFT in Python is to use the pynfft package, which provides a Python wrapper to the C library referenced in the above paper. The advantage of
pynfftis that, compared to
nfft, it provides a more complete set of routines, including multi-dimensional NFFTs, several related extensions, and a range of computing strategies.
The disadvantage is that
pynfftis GPL-licensed (and thus can't be used in much of the more permissively licensed Python scientific world), and has a much more complicated set of dependencies.
pynfftare comparable, with the implementation within
nfftpackage being up to a factor of 2 faster in most cases of interest (see Benchmarks.ipynb for some simple benchmarks).
If you're curious about the implementation and how
nfftattains such performance without a custom compiled extension, see the Implementation Walkthrough notebook.
import numpy as np from nfft import nfft
define evaluation points
x = -0.5 + np.random.rand(1000)
define Fourier coefficients
N = 10000 k = - N // 2 + np.arange(N) f_k = np.random.randn(N)
non-equispaced fast Fourier transform
f = nfft(x, f_k)
For some more examples, see the notebooks in the notebooks directory.
nfftpackage can be installed directly from the Python Package Index:
$ pip install nfft
Unit tests can be run using pytest:
$ pytest --pyargs nfft