Approximate inversion of discrete Fourier integral operators

JOURNAL OF COMPUTATIONAL PHYSICS

卷:446

Article

Feliu-Faba, Jordi¹  Ying, Lexing^1,2 

[1] Stanford Univ, Inst Computat & Math Engn, Stanford, CA 94305 USA

[2] Stanford Univ, Dept Math, Stanford, CA 94305 USA

关键词: Fourier integral operator;    Radon transform;    Hierarchical matrices;    Hierarchical interpolative factorization;    Butterfly algorithm;   

DOI  :  10.1016/j.jcp.2021.110654

来源: Elsevier

【 摘 要 】

This paper introduces a factorization for the inverse of discrete Fourier integral operators of size N x N 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 0 (log N) sparse matrices with 0 (N) entries. 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. (C) 2021 Elsevier Inc. All rights reserved.

【 授权许可】

Free