Approximate Inversion of Discrete Fourier Integral Operators via Hierarchically Semiseparable Matrices
Abstract
This paper introduces a novel method for approximating the inverse of discrete Fourier integral operators (FIOs). Given an N × N matrix representation K of an FIO, the proposed algorithm consists of two stages. In the offline stage, we first construct a butterfly factorization (BF) K̃ of K, which enables fast forward matrix-vector multiplication. We then construct a hierarchically semiseparable (HSS) approximation G̃ ≈ G, where G = K* K, using fast applications of K̃ and K̃* to random matrices. Finally, we apply the ULV factorization to the HSS matrix G̃ to obtain an approximation F̃ ≈ G−1. Combining these approximations yields an approximate inverse K−1 ≈ F̃ K̃*. The offline stage has complexity O(N log2 N) for 1D problems and O(N1.5 log N) for 2D problems. In the online stage, the proposed method approximates K−1 u for a given input vector u with complexity O(N log N) for both 1D and 2D problems. The proposed method can be used either as a direct solver or as a preconditioner for iterative methods. Numerical results for 1D and 2D FIOs demonstrate the effectiveness of the proposed method.
Related
- A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrices
- Scalable Approximate Selected Inversion Based on Single-Level Incomplete LDLT Factorization and Spectral Corrections for Large Sparse Systems
- Agmon estimates for the difference of exact and approximate Dirichlet eigenfunctions for difference operators
- Neural operators approximate strongly continuous convex monotone semigroups
- Approximate maximum likelihood estimation for partially observed fractional diffusions from discrete observations
BibTeX
@misc{li2026approximate,
title = {{Approximate Inversion of Discrete Fourier Integral Operators via Hierarchically Semiseparable Matrices}},
author = {Yingzhou Li and Jingyu Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11520},
eprint = {2609.11520},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11520},
}
RIS
TY - UNPB
TI - Approximate Inversion of Discrete Fourier Integral Operators via Hierarchically Semiseparable Matrices
AU - Yingzhou Li
AU - Jingyu Liu
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11520
UR - https://arxiv.org/abs/2609.11520
AB - This paper introduces a novel method for approximating the inverse of discrete Fourier integral operators (FIOs). Given an N × N matrix representation K of an FIO, the proposed algorithm consists of two stages. In the offline stage, we first construct a butterfly factorization (BF) K̃ of K, which enables fast forward matrix-vector multiplication. We then construct a hierarchically semiseparable (HSS) approximation G̃ ≈ G, where G = K^* K, using fast applications of K̃ and K̃^* to random matrices. Finally, we apply the ULV factorization to the HSS matrix G̃ to obtain an approximation F̃ ≈ G^−1. Combining these approximations yields an approximate inverse K^−1 ≈ F̃ K̃^*. The offline stage has complexity O(N log^2 N) for 1D problems and O(N^1.5 log N) for 2D problems. In the online stage, the proposed method approximates K^−1 u for a given input vector u with complexity O(N log N) for both 1D and 2D problems. The proposed method can be used either as a direct solver or as a preconditioner for iterative methods. Numerical results for 1D and 2D FIOs demonstrate the effectiveness of the proposed method.
ER -