General
A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform
arXiv cs.NA0 views
arXiv:2512.03733v2 Announce Type: replace Abstract: Various fields in scientific computing require the use of the nonuniform discrete Fourier transform (NUDFT) and its inversion. In [H. Wilber, E. N. Epperly, and A. H. Barnett, SIAM J. Sci. Comput., 47 (2025), pp. A1702-A1732], the authors proposed a direct inversion method for the type-II NUDFT, which achieves quasi-linear complexity by approximating the type-II NUDFT matrix as a product of a hierarchical semiseparable (HSS) matrix and a DFT matrix. In this article, we propose a novel superfast direct inversion method for type-III NUDFT. The proposed method approximates the type-III NUDFT matrix as a product of a type-II NUDFT matrix and an HSS matrix. This decomposition enables both the forward application and the backward inversion to be accomplished with quasi-linear complexity. The fast inversion can serve as a high-accuracy direct solver or as an efficient preconditioner. Additionally, we provide an error bound for the approximation when the sample points are independent and identically distributed uniform random variables and the frequencies are perturbed continuous integers. Numerical results are presented to verify the relevant theoretical properties and demonstrate the efficiency of the proposed methods.
Source:https://arxiv.org/abs/2512.03733PreviousFully implicit timestepping methods for the rotating shallow water equationsNextApplications of QR-based Vector-Valued Rational Approximation
Related posts
Joint Optimization of Antenna Partitioning and Distortion-Aware Precoding for Massive MIMO-OFDM with Peak Cancellation and In-Band Distortion Compensation
0arXiv eess.SP
Smoothed estimation of Wasserstein barycenters
0arXiv stat.TH
On Sparsity and Sub-Gaussianity in the Johnson-Lindenstrauss Lemma
0arXiv stat.TH
Applications of QR-based Vector-Valued Rational Approximation
0arXiv cs.NA
Fully implicit timestepping methods for the rotating shallow water equations
0arXiv cs.NA
An iterative tangential interpolation algorithm for model reduction of MIMO systems
0arXiv eess.SY