Approximate inversion of discrete Fourier integral operators

Abstract

This paper introduces a factorization for the inverse of discrete Fourier integral operators that can be applied in quasi-linear time. The factorization starts by approximating the operator with the butterfly factorization. Next, a hierarchical matrix representation is constructed for the hermitian matrix arising from composing the Fourier integral operator with its adjoint. This representation is inverted efficiently with a new algorithm based on the hierarchical interpolative factorization. By combining these two factorizations, an approximate inverse factorization for the Fourier integral operator is obtained as a product of $O(\log N)$ sparse matrices of size $N\times N$. The resulting approximate inverse factorization can be used as a direct solver or as a preconditioner. Numerical examples on 1D and 2D Fourier integral operators, including a generalized Radon transform, demonstrate the performance of this new approach.

References in corpus (9)

• A fast direct solver for structured linear systems by recursive skeletonization
• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• Thermoacoustic tomography arising in brain imaging
• Butterfly Factorization
• A recursive skeletonization factorization based on strong admissibility
• Interpolative Butterfly Factorization
• Multidimensional Butterfly Factorization
• Butterfly factorization via randomized matrix-vector multiplications
• Multidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization