Python
The Python package nfftjl wraps libnfftjl, NFFT.jl compiled into a library with juliac --trim (see C). The wheel carries the library and its Julia runtime; no Julia installation is needed to use it. It covers the NFFT, RNFFT, NFCT, NFST and NNFFT and their adjoints in 1–3 dimensions, with batches, in single and double precision; the table on the home page lists what the Julia package offers beyond that. The interface may still change.
Installation
nfftjl is not on PyPI yet. A wheel for your platform is built from the repository (building needs Julia ≥ 1.12, using the wheel does not):
git clone https://github.com/JuliaMath/NFFT.jl && cd NFFT.jl
libnfftjl/build.sh # the library, ≈ 2 min
python3 -m venv .venv && .venv/bin/pip install numpy build wheel setuptools
PYTHON=.venv/bin/python bindings/python/build_wheel.sh
.venv/bin/pip install bindings/python/dist/*.whlA first transform
The NFFT evaluates $\hat f_j = \sum_{\bm l} f_{\bm l} \, e^{-2\pi i \bm l \cdot \bm k_j}$ at nodes $\bm k_j \in [-1/2, 1/2)^D$ for the equidistant array $f$ (see Mathematical Background); the adjoint is the sum with the opposite sign. This example computes both and checks the first values against the direct sum:
# A 2D NFFT and its adjoint with nfftjl, checked against the direct sum.
import numpy as np
import nfftjl
rng = np.random.default_rng(0)
N = (64, 48) # size of the equidistant array
k = rng.random((1000, 2)) - 0.5 # 1000 nodes in [-1/2, 1/2)², one per row
f = rng.standard_normal(N) + 1j * rng.standard_normal(N)
p = nfftjl.Plan(k, N, reltol=1e-9) # nthreads: all threads of the library
fhat = p.trafo(f) # fhat_j = Σ_l f_l exp(-2πi l·k_j)
g = p.adjoint(fhat) # g_l = Σ_j fhat_j exp(+2πi l·k_j)
# the direct sum at the first ten nodes; l_d = -N_d//2, …, N_d - N_d//2 - 1 along axis d of f
grid = np.meshgrid(*[np.arange(-(n // 2), n - n // 2) for n in N], indexing="ij")
l = np.stack(grid, axis=-1) # shape N + (2,)
ref = np.array([np.sum(f * np.exp(-2j * np.pi * (l @ kj))) for kj in k[:10]])
err = np.linalg.norm(fhat[:10] - ref) / np.linalg.norm(ref)
print(f"relative error {err:.1e}")
assert err < 1e-8Interface
nfftjl.Plan(k, shape, reltol=1e-8, nthreads=None, dtype=numpy.complex128, axes=None) : Plan for the nodes k, an array of shape (J, D) (one node per row; shape (J,) in 1D) with entries in $[-1/2, 1/2)$, and data of shape shape (an integer or a tuple), transformed along axes: all axes by default, otherwise D = 1, 2 or 3 consecutive axes (column d of k belongs to axes[d]). The other axes are batch axes, see Batches. reltol is the requested relative error: window, window width and oversampling factor are chosen for it at the lowest predicted cost (see Accuracy and Parameters). nthreads defaults to num_threads(). dtype is the element type of the data, numpy.complex128 or numpy.complex64; the nodes are given in double precision either way, and grid positions are computed from them in double precision.
p.trafo(f, out=None) : The NFFT of f (shape p.shape, converted to dtype): an array of shape p.out_shape, the transformed axes replaced by one axis of length J.
p.adjoint(fhat, out=None) : The adjoint NFFT of fhat (shape p.out_shape): an array of shape p.shape.
p.close() : Releases the plan; garbage collection does the same.
nfftjl.num_threads() : The default number of threads of a plan: the environment variable NFFTJL_NUM_THREADS if set, otherwise the number of performance cores (Apple Silicon) or of all CPU threads. The library has one thread per CPU thread, the upper limit of nthreads.
Along axis d of f, index i stands for the frequency $l_d = i - N_d/2$ ($N_d/2$ rounded down), in increasing order, as numpy.fft.fftshift orders them. Arrays in numpy's default (C) order are passed to the library without a copy. With out the result goes into an existing array.
The transform equals FINUFFT's type 2 with x = 2π k, isign = -1 and the default mode ordering; the adjoint equals type 1 with isign = +1.
Real data: RNFFT, NFCT, NFST
nfftjl.RNFFTPlan, nfftjl.NFCTPlan and nfftjl.NFSTPlan take the same arguments as Plan (dtype is the real type, numpy.float64 or numpy.float32); p.in_shape and p.out_shape give the shapes of their data:
- RNFFT (real values at the nodes): $\hat f_j = \mathrm{Re} \sum_{\bm n} h_{\bm n} e^{-2\pi i \bm n \cdot \bm k_j}$ with $n = 0, \dots, N/2$ along the last transformed axis (the layout of
numpy.fft.rfftn) and as for the NFFT along the others;his complex, the values at the nodes are real. The adjoint is $h_{\bm n} = \sum_j \hat f_j e^{2\pi i \bm n \cdot \bm k_j}$. Nodes in $[-1/2, 1/2)$. - NFCT and NFST: $\hat f_j = \sum_{\bm n} f_{\bm n} \prod_d \cos(2\pi n_d k_{dj})$ over $n_d = 0, \dots, N_d - 1$, or with $\sin$ over $n_d = 1, \dots, N_d$, for real
f;adjointis the transpose. Nodes in $[0, 1/2]$.
# The transforms for real data: an NFCT in 2D checked against its direct sum, and an RNFFT whose
# coefficients have the layout of numpy.fft.rfftn.
import numpy as np
import nfftjl
rng = np.random.default_rng(2)
N = (32, 24)
k = rng.random((500, 2)) / 2 # NFCT/NFST nodes in [0, 1/2]
f = rng.standard_normal(N)
p = nfftjl.NFCTPlan(k, N, reltol=1e-9)
fhat = p.trafo(f) # sum_n f_n cos(2π n_1 k_1) cos(2π n_2 k_2)
n1, n2 = np.meshgrid(np.arange(N[0]), np.arange(N[1]), indexing="ij")
ref = np.array([np.sum(f * np.cos(2 * np.pi * n1 * x) * np.cos(2 * np.pi * n2 * y)) for x, y in k])
err = np.linalg.norm(fhat - ref) / np.linalg.norm(ref)
print(f"NFCT: relative error {err:.1e}")
assert err < 1e-8
q = nfftjl.RNFFTPlan(rng.random((500, 2)) - 0.5, N)
print("RNFFT: coefficients", q.in_shape, "complex, values at the nodes", q.out_shape, "real")
assert q.in_shape == (32, 13) and q.trafo(np.ones(q.in_shape, dtype=complex)).dtype == np.float64A plan whose nodes lie outside the range of its transform raises a ValueError with the reason.
Non-equidistant in both domains: NNFFT
nfftjl.NNFFTPlan(k, y, shape=None, reltol=1e-8, nthreads=None, dtype=numpy.complex128, axis=-1) computes $\hat f_j = \sum_l f_l e^{-2\pi i \bm k_j \cdot \bm y_l}$ for targets k (shape (J, D)) and sources y (shape (N, D)) with arbitrary real coordinates, and the adjoint. The cost grows with the product of the extents of k and y, not with J and N. With shape, the data have batch axes around axis, the axis of the sources, which the transform replaces by the J targets. It equals FINUFFT's type 3 with x = 2π y, s = k, isign = -1.
# NNFFT: sums of exponentials at arbitrary real frequencies and positions, here a 2D signal of
# point sources sampled at scattered frequencies, checked against the direct sum.
import numpy as np
import nfftjl
rng = np.random.default_rng(3)
y = 50 * rng.random((2000, 2)) # source positions
k = 3 * rng.random((5000, 2)) - 1.5 # frequencies
f = rng.standard_normal(2000) + 1j * rng.standard_normal(2000)
p = nfftjl.NNFFTPlan(k, y, reltol=1e-9)
fhat = p.trafo(f) # sum_l f_l exp(-2πi k_j·y_l)
ref = np.exp(-2j * np.pi * k[:100] @ y.T) @ f
err = np.linalg.norm(fhat[:100] - ref) / np.linalg.norm(ref)
print(f"NNFFT: {len(f)} sources, {len(fhat)} targets, relative error {err:.1e}")
assert err < 1e-8Batches
Every slice along the batch axes is transformed with the same nodes, for example the coil images in MRI. One plan for all slices is faster than a loop over slices: the nodes are binned once, and the batch kernels of NFFT.jl process several slices per pass over the nodes.
# Many transforms with the same nodes: eight coil images of 128 × 128, transformed along axes 1 and 2
# with one plan, compared with one plan per coil.
import numpy as np
import nfftjl
rng = np.random.default_rng(1)
k = rng.random((20_000, 2)) - 0.5 # nodes, one per row
images = rng.standard_normal((8, 128, 128)) + 0j # coil × x × y
p = nfftjl.Plan(k, images.shape, axes=(1, 2)) # axis 0 is a batch axis
data = p.trafo(images) # shape (8, 20000)
back = p.adjoint(data) # shape (8, 128, 128)
single = nfftjl.Plan(k, (128, 128))
ref = np.stack([single.trafo(images[c]) for c in range(8)])
err = np.linalg.norm(data - ref) / np.linalg.norm(ref)
print(f"shape {data.shape}, difference to single plans {err:.1e}")
assert data.shape == (8, 20_000) and back.shape == images.shape and err < 1e-12Threads
- One plan must not be executed by two threads at the same time: create one plan per thread. Separate plans run concurrently, each with its own
nthreads. - The default number of threads of a plan is the environment variable
NFFTJL_NUM_THREADSif set, otherwise the number of performance cores on Apple Silicon and of all CPU threads elsewhere. A 1D transform runs its FFT in one piece per thread, so a thread on an efficiency core or on a core busy with other work holds it up (up to 2× slower with all 10 threads of an M1 Max); on a busy machine fewer threads than cores are faster. - numpy's OpenBLAS threads keep spinning for a while after a numpy call and slow down a transform that follows;
OPENBLAS_NUM_THREADS=1avoids this when timing.
Comparison with FINUFFT
bindings/python/tests/bench.py compares nfftjl with FINUFFT's Python package on the problems of the Performance page. The library runs the same machine code as the Julia package.