C
libnfftjl is NFFT.jl compiled into a shared library with juliac --trim. It carries its Julia runtime; programs that use it need no Julia installation. It covers the NFFT, RNFFT, NFCT, NFST and NNFFT and their adjoints in 1–3 dimensions, with batches, in single and double precision (functions nfftjl_rnfft_…, nfftjl_nfct_…, nfftjl_nfst_…, nfftjl_nnfft_…, see the header below); the table on the home page lists what the Julia package offers beyond that. The interface may still change.
Building
Building needs Julia ≥ 1.12:
git clone https://github.com/JuliaMath/NFFT.jl && cd NFFT.jl
libnfftjl/build.shThe result is libnfftjl/build/: lib/libnfftjl.so (.dylib on macOS) next to the Julia runtime it needs, and the artifacts (FFTW) in share/. Keep the directory together. A program compiles against the header libnfftjl/include/nfftjl.h:
cc -O2 prog.c -Ilibnfftjl/include -Llibnfftjl/build/lib -lnfftjl -lm -Wl,-rpath,$PWD/libnfftjl/build/libThe library starts one Julia thread per CPU thread; a plan uses nthreads of them, by default the value of the environment variable NFFTJL_NUM_THREADS or one per performance core. It is built with Julia's signal handling, which the garbage collector needs to stop threads, and for one CPU target (see libnfftjl/README.md).
A 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 program computes both and checks the first values against the direct sum:
/* A 2D NFFT and its adjoint with libnfftjl, checked against the direct sum.
cc -O2 getting_started.c -I../include -L../build/lib -lnfftjl -lm -Wl,-rpath,../build/lib */
#include <complex.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "nfftjl.h"
int main(void) {
const int D = 2;
const int64_t N[] = {64, 48}, J = 1000; /* array size, number of nodes */
const int64_t M = N[0] * N[1];
/* column major: node j is k[2j], k[2j+1]; f[l0 + N0*l1] */
double *k = malloc(sizeof(double) * D * J);
double complex *f = malloc(sizeof(double complex) * M), *fhat = malloc(sizeof(double complex) * J),
*g = malloc(sizeof(double complex) * M);
srand(0);
for (int64_t i = 0; i < D * J; i++) k[i] = rand() / (RAND_MAX + 1.0) - 0.5;
for (int64_t i = 0; i < M; i++) f[i] = rand() / (RAND_MAX + 1.0) - 0.5;
int64_t p = nfftjl_plan_create(D, N, J, k, 1e-9, nfftjl_num_threads());
if (p < 0) return 1;
nfftjl_trafo(p, f, fhat); /* fhat_j = Σ_l f_l exp(-2πi l·k_j) */
nfftjl_adjoint(p, fhat, g); /* 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 */
double e = 0, s = 0;
for (int64_t j = 0; j < 10; j++) {
double complex ref = 0;
for (int64_t l1 = 0; l1 < N[1]; l1++)
for (int64_t l0 = 0; l0 < N[0]; l0++)
ref += f[l0 + N[0] * l1] *
cexp(-2 * M_PI * I * ((l0 - N[0] / 2) * k[D * j] + (l1 - N[1] / 2) * k[D * j + 1]));
e += pow(cabs(fhat[j] - ref), 2); s += pow(cabs(ref), 2);
}
printf("relative error %.1e\n", sqrt(e / s));
nfftjl_plan_destroy(p);
free(k); free(f); free(fhat); free(g);
return sqrt(e / s) < 1e-8 ? 0 : 1;
}Interface
/* NFFT.jl as a C library (built with juliac --trim). Arrays are column major (Julia order):
nodes k[d + D*j] in [-1/2, 1/2), coefficients f of size N[0] x ... x N[D-1],
fhat_j = sum_l f_l exp(-2 pi i l.k_j), l = -N/2 ... N-N/2-1 in every dimension. */
#ifndef NFFTJL_H
#define NFFTJL_H
#include <stddef.h>
#include <stdint.h>
#include <complex.h>
/* A plan for D = 1..3 dimensions, J nodes, relative error reltol, using nthreads threads
(0: the default, nfftjl_num_threads()); -1 on error. */
int64_t nfftjl_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int nfftjl_trafo(int64_t plan, const double complex *f, double complex *fhat);
int nfftjl_adjoint(int64_t plan, const double complex *fhat, double complex *f);
int nfftjl_plan_destroy(int64_t plan);
/* The message of the last failed plan creation, written into buf (len bytes, zero-terminated,
truncated); returns the length of the whole message. */
size_t nfftjl_last_error(char *buf, size_t len);
/* A plan for many transforms with the same nodes: data of size L1 x N[0] x ... x N[D-1] x L3 and
L1 x J x L3 (column major), the transforms along the dimensions in between. */
int64_t nfftjl_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
/* RNFFT (real values at the nodes): fhat_j = Re sum_n h_n exp(-2 pi i n.k_j) over n_0 = 0 ... N[0]/2
and the other n_d as above; h has N[0]/2+1 x N[1] x ... complex values, fhat J real values.
The adjoint: h_n = sum_j fhat_j exp(2 pi i n.k_j). */
int64_t nfftjl_rnfft_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjl_rnfft_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjl_rnfft_trafo(int64_t plan, const double complex *h, double *fhat);
int nfftjl_rnfft_adjoint(int64_t plan, const double *fhat, double complex *h);
/* NFCT and NFST (real data, nodes in [0, 1/2]): fhat_j = sum_n f_n prod_d cos(2 pi n_d k_dj) over
n_d = 0 ... N[d]-1 (NFCT), or with sin over n_d = 1 ... N[d] (NFST); the adjoint is the
transpose. */
int64_t nfftjl_nfct_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjl_nfct_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjl_nfct_trafo(int64_t plan, const double *f, double *fhat);
int nfftjl_nfct_adjoint(int64_t plan, const double *fhat, double *f);
int64_t nfftjl_nfst_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjl_nfst_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjl_nfst_trafo(int64_t plan, const double *f, double *fhat);
int nfftjl_nfst_adjoint(int64_t plan, const double *fhat, double *f);
/* NNFFT (nonequispaced in both domains): fhat_j = sum_l f_l exp(-2 pi i k_j.y_l) for J targets
k[d + D*j] and N sources y[d + D*l], arbitrary real coordinates; the adjoint is
f_l = sum_j fhat_j exp(2 pi i k_j.y_l). The cost grows with the product of the extents of k and y,
not with J and N. _many: data of size L1 x N x L3 and L1 x J x L3. */
int64_t nfftjl_nnfft_plan_create(int D, int64_t J, const double *k, int64_t N, const double *y, double reltol,
int nthreads);
int64_t nfftjl_nnfft_plan_create_many(int D, int64_t J, const double *k, int64_t N, const double *y, int64_t L1,
int64_t L3, double reltol, int nthreads);
int nfftjl_nnfft_trafo(int64_t plan, const double complex *f, double complex *fhat);
int nfftjl_nnfft_adjoint(int64_t plan, const double complex *fhat, double complex *f);
/* Plans of all transforms are released by nfftjl_plan_destroy. */
/* The same in single precision (data in float complex; nodes and reltol stay double). */
int64_t nfftjlf_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjlf_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjlf_trafo(int64_t plan, const float complex *f, float complex *fhat);
int nfftjlf_adjoint(int64_t plan, const float complex *fhat, float complex *f);
int nfftjlf_plan_destroy(int64_t plan);
int64_t nfftjlf_rnfft_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjlf_rnfft_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjlf_rnfft_trafo(int64_t plan, const float complex *h, float *fhat);
int nfftjlf_rnfft_adjoint(int64_t plan, const float *fhat, float complex *h);
int64_t nfftjlf_nfct_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjlf_nfct_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjlf_nfct_trafo(int64_t plan, const float *f, float *fhat);
int nfftjlf_nfct_adjoint(int64_t plan, const float *fhat, float *f);
int64_t nfftjlf_nfst_plan_create(int D, const int64_t *N, int64_t J, const double *k, double reltol, int nthreads);
int64_t nfftjlf_nfst_plan_create_many(int D, const int64_t *N, int64_t J, const double *k, int64_t L1, int64_t L3,
double reltol, int nthreads);
int nfftjlf_nfst_trafo(int64_t plan, const float *f, float *fhat);
int nfftjlf_nfst_adjoint(int64_t plan, const float *fhat, float *f);
int64_t nfftjlf_nnfft_plan_create(int D, int64_t J, const double *k, int64_t N, const double *y, double reltol,
int nthreads);
int64_t nfftjlf_nnfft_plan_create_many(int D, int64_t J, const double *k, int64_t N, const double *y, int64_t L1,
int64_t L3, double reltol, int nthreads);
int nfftjlf_nnfft_trafo(int64_t plan, const float complex *f, float complex *fhat);
int nfftjlf_nnfft_adjoint(int64_t plan, const float complex *fhat, float complex *f);
/* 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
starts one Julia thread per CPU thread, which is also the upper limit for nthreads). Plans can be created and
destroyed from any thread; one plan must not be executed on two threads at once. The Julia
runtime starts on the first call into the library: make that call from one thread before
others call concurrently (nfftjl_num_threads() will do). */
int nfftjl_num_threads(void);
#endifnfftjl_plan_create(D, N, J, k, reltol, nthreads) : A plan for D = 1, 2, 3 dimensions, the array size N[0..D-1] and J nodes k ($D \times J$, column major: node j is k[D*j], …, k[D*j + D-1], entries in $[-1/2, 1/2)$). 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). As in Julia, a reltol that no parameters reach is an error rather than a less accurate plan. The library is compiled for window widths $W = 4, \dots, 16$ (single precision: $4, \dots, 8$), which covers the tolerances that the planner accepts in each precision; the NNFFT chooses both of its windows within this range. nthreads = 0 uses nfftjl_num_threads(). Returns a handle, or −1 on error (nfftjl_last_error gives the message). The nodes are copied.
nfftjl_trafo(p, f, fhat), nfftjl_adjoint(p, fhat, f) : The NFFT of f ($N_0 \times \dots \times N_{D-1}$ complex values, column major: element $(i_0, \dots, i_{D-1})$ at $i_0 + N_0 (i_1 + N_1 (i_2 \dots))$) into fhat (J values), and the adjoint. Index $i_d$ stands for the frequency $l_d = i_d - \lfloor N_d/2 \rfloor$. Return 0, or −1 for an unknown handle.
nfftjl_plan_create_many(D, N, J, k, L1, L3, reltol, nthreads) : A plan for many transforms with the same nodes: the data are $L_1 \times N_0 \times \dots \times N_{D-1} \times L_3$ and $L_1 \times J \times L_3$ (column major), transformed along the dimensions in between. nfftjl_plan_create is the case $L_1 = L_3 = 1$.
nfftjl_plan_destroy(p) : Releases the plan.
nfftjlf_plan_create, nfftjlf_plan_create_many, nfftjlf_trafo, nfftjlf_adjoint, nfftjlf_plan_destroy : The same in single precision: data in float complex; the nodes and reltol stay double, and grid positions are computed from the nodes in double precision. A plan belongs to one precision: the functions of the other return −1.
nfftjl_nnfft_plan_create(D, J, k, N, y, reltol, nthreads), nfftjl_nnfft_plan_create_many(D, J, k, N, y, L1, L3, reltol, nthreads) : The NNFFT $\hat f_j = \sum_l f_l e^{-2\pi i \bm k_j \cdot \bm y_l}$ from N sources y to J targets k (both $D \times$ count, column major, arbitrary real coordinates); data of $L_1 \times N \times L_3$ and $L_1 \times J \times L_3$ complex values. The cost grows with the product of the extents of k and y, not with J and N (see Non-equidistant in Both Domains). nfftjl_nnfft_trafo, nfftjl_nnfft_adjoint and the nfftjlf_nnfft_… functions as for the NFFT.
nfftjl_num_threads() : The default number of threads of a plan: 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.
Row-major data of size $N_0 \times \dots \times N_{D-1}$ is column-major data of the reversed size: pass the sizes and the coordinates of each node in reversed order (the Python package does this).
Batches
One plan for many transforms with the same nodes is faster than a loop over single transforms: the nodes are binned once, and the batch kernels of NFFT.jl process several transforms per pass over the nodes.
/* Many transforms with the same nodes: L = 8 images of 128 x 128, stored one after the other
(column major: 128 x 128 x 8, the batch after the transformed dimensions), with one plan,
compared with one plan per image. */
#include <complex.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "nfftjl.h"
int main(void) {
const int D = 2;
const int64_t N[] = {128, 128}, J = 20000, L = 8, M = 128 * 128;
double *k = malloc(sizeof(double) * D * J);
double complex *f = malloc(sizeof(double complex) * M * L), *fhat = malloc(sizeof(double complex) * J * L),
*ref = malloc(sizeof(double complex) * J);
srand(1);
for (int64_t i = 0; i < D * J; i++) k[i] = rand() / (RAND_MAX + 1.0) - 0.5;
for (int64_t i = 0; i < M * L; i++) f[i] = rand() / (RAND_MAX + 1.0) - 0.5;
/* L1 = 1 (nothing before the transformed dimensions), L3 = L (the images) */
int64_t p = nfftjl_plan_create_many(D, N, J, k, 1, L, 1e-8, 0);
nfftjl_trafo(p, f, fhat); /* fhat: J x L, image l at fhat + J*l */
int64_t q = nfftjl_plan_create(D, N, J, k, 1e-8, 0);
double e = 0, s = 0;
for (int64_t l = 0; l < L; l++) {
nfftjl_trafo(q, f + M * l, ref);
for (int64_t j = 0; j < J; j++) { e += pow(cabs(fhat[J * l + j] - ref[j]), 2); s += pow(cabs(ref[j]), 2); }
}
printf("difference to single plans %.1e\n", sqrt(e / s));
nfftjl_plan_destroy(p); nfftjl_plan_destroy(q);
free(k); free(f); free(fhat); free(ref);
return sqrt(e / s) < 1e-12 ? 0 : 1;
}Threads
- The Julia runtime starts on the first call into the library. Make that call from one thread before other threads call (
nfftjl_num_threads()will do). - Plans can be created and destroyed from any thread. One plan must not be executed by two threads at the same time.
- Separate plans can be executed by several threads at the same time, each with its own
nthreads. - The default number of threads of a plan (
nthreads = 0) isNFFTJL_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.
MATLAB and Octave
bindings/matlab/ wraps the library for MATLAB (R2018a or later) and Octave: a MEX gateway nfftjl_mex.c and a handle class nfftjl.Plan for all transforms of the library, in single and double precision. Arrays are column major as in C, so data and nodes are passed as they are: nodes k as a $D \times J$ matrix in $[-1/2, 1/2)$ (NFCT, NFST: $[0, 1/2]$), coefficients of size N.
build_nfftjl % once: compiles nfftjl_mex against libnfftjl/build/lib
p = nfftjl.Plan(rand(2, 1e4) - 0.5, [256 256], 'reltol', 1e-8);
fhat = p.trafo(randn(256) + 1i * randn(256));
f = p.adjoint(fhat);
q = nfftjl.Plan(k, [64 64], 'kind', 'nfct', 'single', true); % 'rnfft', 'nfct', 'nfst', 'nnfft'The options are 'kind', 'reltol' (default $10^{-8}$), 'single' and 'nthreads'; the NNFFT takes the sources instead of the size, nfftjl.Plan(k, y, 'kind', 'nnfft'). Inputs are converted to the plan's precision. test_nfftjl.m compares all transforms with the direct sums (octave --eval "run('bindings/matlab/test_nfftjl.m')"). Tested with Octave 11.3 on macOS.