FINUFFT is a multi-threaded library to compute efficiently the three most common types of nonuniform fast Fourier transform (NUFFT) to a specified precision, in one, two, or three dimensions, on a multi-core shared-memory machine. It is extremely fast (typically achieving \(10^6\) to \(10^8\) points per second), has very simple interfaces to most major numerical languages (C/C++, Fortran, MATLAB, octave, python, and julia), but also has more advanced (vectorized and “guru”) interfaces that allow multiple st
As an example, given \(M\) real numbers \(x_j \in [0,2\pi)\) , and complex numbers \(c_j\) , with \(j=1,\dots,M\) , and a requested integer number of modes \(N\) , FINUFFT can efficiently compute the 1D “type 1” transform, which means to evaluate the \(N\) complex outputs
As with other “fast” algorithms, FINUFFT does not evaluate this sum directly—which would take \(O(NM)\) effort—but rather uses a sequence of steps (in this case, optimally chosen spreading, FFT, and deconvolution) to approximate the vector of answers (1) to within the user’s desired relative tolerance, with only \(O(N \log N +M)\) effort, ie, in almost linear time. Thus the speed-up is similar to that of the FFT. You may now want to jump to quickstart , or see the definitions of the other transforms in gene