InvNUDFT

MATLAB research code for the fast direct inversion of nonuniform discrete Fourier transforms (NUDFTs).

Mathematical problems

1D Type-II NUDFT

$$f_{j} = \sum_{k = 0}^{N - 1} e^{-2 \pi \mathrm{i} k x_{j}} c_{k}, \quad 0 \leq j \leq M - 1.$$

Here, the sample points ${x_{j}}$ are distributed arbitrarily in $[0,1)$, while the frequencies ${k}$ lie on a contiguous integer grid. The coefficients ${c_{k}}$ and the target values ${f_{j}}$ are assumed to be complex-valued.

The numbers of sample points and frequencies are denoted by $M$ and $N$, respectively.

2D Type-II NUDFT

$$f_{j} = \sum_{k^{[x]} = 0}^{n^{[x]} - 1} \sum_{k^{[y]} = 0}^{n^{[y]} - 1} e^{-2 \pi \mathrm{i} \bigl(k^{[x]} x_{j} + k^{[y]} y_{j}\bigr)} c_{k^{[x]}, k^{[y]}}, \quad 0 \leq j \leq M - 1.$$

Here, the sample points ${(x_{j}, y_{j})}$ are distributed arbitrarily in $[0, 1)^{2}$, while the frequencies ${(k^{[x]}, k^{[y]})}$ lie on a Cartesian grid of contiguous integers. The coefficients ${c_{k^{[x]}, k^{[y]}}}$ and the target values ${f_{j}}$ are assumed to be complex-valued.

The numbers of sample points and frequencies are denoted by $M$ and $N = n^{[x]} n^{[y]}$, respectively.

Installation

Clone the repository:

git clone https://github.com/JingyuLiuMath/InvNUDFT.git
cd InvNUDFT

Install FINUFFT

We strongly recommend using mip to install FINUFFT.

mip

To install mip, run the following command in the MATLAB Command Window:

eval(webread('https://mip.sh/install.txt'))

FINUFFT

To install FINUFFT, run:

mip install finufft

Set the MATLAB path

Start MATLAB from the repository root and run:

invnudft_startup();

Running the tests

From the repository root, run:

% Test the 2D Type-II problem on a random uniform grid.
run("test/typeII_2d/test_typeII_2d_rand.m");

The test has been successfully run on both Windows and Linux with the following software versions:

• MATLAB R2023b;
• mip 1.0.0;
• FINUFFT 2.5.1.

Reproducing the experiments

The numerical experiments are located in the following directories:

• experiments/typeII_2d_rand/ — 2D Type-II problem on a random uniform grid;
• experiments/typeII_2d_polar/ — 2D Type-II problem on a modified polar grid.

Developers

• Yingzhou Li, School of Mathematical Sciences, Fudan University;
• Jingyu Liu, School of Mathematical Sciences, Fudan University.

Related papers

• Heather Wilber, Ethan N. Epperly, and Alex H. Barnett, Superfast direct inversion of the nonuniform discrete Fourier transform via hierarchically semiseparable least squares, SIAM Journal on Scientific Computing, 47 (2025), pp. A1702–A1732.
• Yingzhou Li and Jingyu Liu, A superfast direct solver for 2D Type-II inverse nonuniform discrete Fourier transform based on hierarchically semiseparable matrix, arXiv:2607.00928, 2026.