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.

Development version

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 → equidistant

Python (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 → equidistant

C (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.

JuliaPythonCMATLAB/Octave
NFFT and adjoint, reltol chooses the parameters✓✓✓✓
dimensionsany (tested for 1–5)1–31–31–3
precisionFloat32, Float64complex64, complex128float, doublesingle, double
multi-threaded✓✓✓✓
transforms along dimensions (batches)✓✓✓–
RNFFT, NFCT, NFST✓✓✓✓
NNFFT✓✓✓✓
GPUs✓–––
stages, density compensation, Toeplitz✓–––
status1.0 (in development)experimentalexperimentalexperimental

What NFFT.jl offers

  • You ask for an accuracy, not for parameters. reltol is 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, and accuracy(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.jl defines 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:

Explanation, for understanding:

Reference, to look things up:

  • API: all exported functions and types.
  • Abstract Interface: AbstractNFFTs.jl and 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

The complete list is on GitHub.