A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911300245782528 |
|---|---|
| author | Li, Yingzhou Liu, Jingyu |
| author_facet | Li, Yingzhou Liu, Jingyu |
| contents | The nonuniform discrete Fourier transform (NUDFT) and its inverse are widely used in various fields of scientific computing. 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, where the type-II NUDFT matrix is further decomposed into the product of an HSS matrix and an uniform discrete Fourier transform (DFT) matrix as in [Wilber, Epperly, and Barnett, SIAM Journal on Scientific Computing, 47(3):A1702-A1732, 2025]. 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 under specific sample distributions. Numerical results are presented to verify the relevant theoretical properties and demonstrate the efficiency of the proposed methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03733 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform Li, Yingzhou Liu, Jingyu Numerical Analysis The nonuniform discrete Fourier transform (NUDFT) and its inverse are widely used in various fields of scientific computing. 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, where the type-II NUDFT matrix is further decomposed into the product of an HSS matrix and an uniform discrete Fourier transform (DFT) matrix as in [Wilber, Epperly, and Barnett, SIAM Journal on Scientific Computing, 47(3):A1702-A1732, 2025]. 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 under specific sample distributions. Numerical results are presented to verify the relevant theoretical properties and demonstrate the efficiency of the proposed methods. |
| title | A Superfast Direct Solver for Type-III Inverse Nonuniform Discrete Fourier Transform |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2512.03733 |