NFFT.jl
Fast Fourier transforms at non-equidistant nodes: a Julia package for CPUs and GPUs, and a library for Python and C compiled from the same code.
This documentation describes NFFT.jl 1.0, which is under development on the branch refactoring (PR #177) and not released yet. Pkg.add("NFFT") installs version 0.14, documented here. See Migrating from NFFT.jl 0.x.
NFFT.jl computes the non-equidistant fast Fourier transform (NFFT, also called NUFFT, or gridding in MRI): a discrete Fourier transform where the nodes in one domain do not lie on a grid. It is accurate to a tolerance you choose and runs in $\mathcal{O}(|\bm{N}| \log |\bm{N}| + J)$ operations for $J$ nodes and an array of size $\bm{N}$. The same plans run multi-threaded on the CPU and on GPUs (CUDA, AMD, Apple).
Quick start
Julia
using NFFT
k = rand(2, 10_000) .- 0.5 # 10 000 nodes in [-1/2, 1/2)²
f = randn(ComplexF64, 256, 256) # equidistant data
p = plan_nfft(k, size(f)) # relative error 1e-8 by default
fHat = p * f # NFFT: equidistant → nodes
g = adjoint(p) * fHat # adjoint NFFT: nodes → equidistantPython (experimental, see Python)
import numpy as np
import nfftjl
k = np.random.rand(10_000, 2) - 0.5 # 10 000 nodes in [-1/2, 1/2)², one per row
f = np.random.randn(256, 256) + 0j # equidistant data
p = nfftjl.Plan(k, f.shape) # relative error 1e-8 by default
fhat = p.trafo(f) # NFFT: equidistant → nodes
g = p.adjoint(fhat) # adjoint NFFT: nodes → equidistantC (experimental, see C)
#include "nfftjl.h"
int64_t N[] = {256, 256}; /* column major: node j is k[2j], k[2j+1] */
int64_t p = nfftjl_plan_create(2, N, J, k, 1e-8, nfftjl_num_threads());
nfftjl_trafo(p, f, fhat); /* NFFT: equidistant → nodes */
nfftjl_adjoint(p, fhat, g); /* adjoint NFFT: nodes → equidistant */
nfftjl_plan_destroy(p);What is available in which language
The Julia package is the full library. Python, C and MATLAB/Octave use libnfftjl, a library compiled from the same Julia code with juliac --trim: no Julia installation is needed to use it, and it is as fast as the Julia package. Its interface is experimental and covers the core transform so far.
| Julia | Python | C | MATLAB/Octave | |
|---|---|---|---|---|
NFFT and adjoint, reltol chooses the parameters | ✓ | ✓ | ✓ | ✓ |
| dimensions | any (tested for 1–5) | 1–3 | 1–3 | 1–3 |
| precision | Float32, Float64 | complex64, complex128 | float, double | single, double |
| multi-threaded | ✓ | ✓ | ✓ | ✓ |
| transforms along dimensions (batches) | ✓ | ✓ | ✓ | – |
| RNFFT, NFCT, NFST | ✓ | ✓ | ✓ | ✓ |
| NNFFT | ✓ | ✓ | ✓ | ✓ |
| GPUs | ✓ | – | – | – |
| stages, density compensation, Toeplitz | ✓ | – | – | – |
| status | 1.0 (in development) | experimental | experimental | experimental |
What NFFT.jl offers
- You ask for an accuracy, not for parameters.
reltolis all you need to set. The plan picks the window function, its width and the oversampling factor that reach this error at the lowest predicted cost, andaccuracy(p)tells you what it expects to achieve. - CPU and GPU from one code base. Every transform, including batch dimensions, runs on the GPU when the plan gets a GPU array type:
plan_nfft(k, N; storage=CuArray). The GPU kernels are written with KernelAbstractions.jl and serve CUDA, AMD and Apple GPUs alike; see GPU. - Fast. Tiled resampling with piecewise-polynomial window evaluation, an FFT that skips the zero padding, and multi-threading in every stage. See Performance for a comparison with FINUFFT and ducc.
- Transforms along some dimensions of an array (
dims), with batch kernels that process many transforms with the same nodes at once, as needed for multi-coil MRI or OCT. - Real data at the nodes (
plan_rnfft, e.g. OCT), on a real grid. - Cosine and sine transforms (NFCT, NFST) for real data, with the definitions of NFFT3 and about the cost of a complex NFFT.
- Non-equidistant points in both domains (NNFFT,
plan_nnfft). - Single and double precision, with node positions always computed in double precision.
- The three stages of the algorithm as an interface: resampling correction, FFT and resampling can be called one by one, for example to embed the NFFT into a Toeplitz approach or to profile it.
- Automatic differentiation with Zygote (ChainRules) and Enzyme: a plan is a constant linear map, its derivative is the plan itself or its adjoint.
- One interface for several implementations.
AbstractNFFTs.jldefines plans, options and operations; NFFT.jl and NonuniformFFTs.jl implement it. Code written against the interface runs with each of them.
Installation
using Pkg
Pkg.add("NFFT")This also installs AbstractNFFTs.jl, the interface package. Sampling density compensation and Toeplitz kernels are in NFFTTools.jl (Pkg.add("NFFTTools")). For Python and C see Python and C.
Guide
The documentation follows the Diátaxis structure:
Getting started, to learn NFFT.jl step by step:
- Getting Started in Julia: plans, transforms, precision, threads and changing nodes.
- Python and C: installation, a first transform, the interface, threads.
How-to guides (Julia), for a task at hand:
- Transforms along Dimensions:
dimsand many transforms with the same nodes. - Real Data: real values at the nodes with
plan_rnfft(e.g. OCT). - Cosine and Sine Transforms: the NFCT and NFST.
- Non-equidistant in Both Domains: the NNFFT.
- GPU: all transforms on GPUs.
- Density Compensation and Toeplitz Kernels:
NFFTTools.jl. - Choosing Parameters: window, width, oversampling and FFT planning by hand.
- Stages of the NFFT: calling the stages one by one.
- Migrating from NFFT.jl 0.x: what changed in version 1.0.
Explanation, for understanding:
- Mathematical Background: the transforms and the three stages of the algorithm.
- Accuracy and Parameters: how
reltolbecomes window, width and oversampling. - How NFFT.jl Works: tiles, halo, pruned FFT, batches, real data, NNFFT and GPUs, with the ideas behind them.
- Performance: NFFT.jl against FINUFFT, ducc and NonuniformFFTs.jl.
Reference, to look things up:
- API: all exported functions and types.
- Abstract Interface:
AbstractNFFTs.jland how to write an implementation.
Citing
The source code is licensed under the MIT license. If you use NFFT.jl in your work, please cite
T. Knopp, M. Boberg and M. Grosser, NFFT.jl: Generic and Fast Julia Implementation of the Nonequidistant Fast Fourier Transform, SIAM Journal on Scientific Computing 45(3), C179–C205, 2023 (arXiv:2208.00049).
A BibTeX entry is in NFFT.bib in the root of the repository.
Contact
Bugs and ideas go to the issue tracker, questions to the discussions.
Contributors
- Tobias Knopp
- Niklas Hackelberg
- Robert Dahl Jacobsen
- Mirco Grosser
- Jakob Assländer
- Mosè Giordano
- Jeff Fessler
The complete list is on GitHub.