A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrix

This paper proposes a direct inversion method for the 2D type-II nonuniform discrete Fourier transform~(NUDFT).

The NUDFT matrix $A$ is factored as $A = G F$, where $G$ can be expressed as a kernel matrix and $F$ is the 2D DFT matrix.

We show that $G$ can be approximated by a hierarchically semiseparable~(HSS) matrix and give an estimate of the HSS rank.

Then, using the least-squares solver for HSS matrix and the two-dimensional inverse fast Fourier transform, the inverse NUDFT problem can be solved efficiently.

Our algorithm has an offline complexity of $O\bigl(M+ N^{3 / 2} \log^{3} N\bigr)$ where $M$ and $N$ are the size of rows and columns of the NUDFT matrix, respectively.

Once the direct solver is built, it can be applied to a vector with an online complexity of $O\bigl(M+ N \log^{3} N\bigr)$.

The proposed method can be used as a preconditioner for iterative methods, especially when the sample points are distributed on a grid such that $A$ is ill-conditioned.

Numerical results are provided to show the scaling performance of the inversion method and demonstrate the efficiency and robustness of it as a preconditioner.