A unified framework for oscillatory integral transforms: When to use NUFFT or butterfly factorization?

JOURNAL OF COMPUTATIONAL PHYSICS

卷:388

Article

Yang, Haizhao¹ 

[1] Natl Univ Singapore, Dept Math, Singapore, Singapore

关键词: Non-uniform fast Fourier transform;    Butterfly factorization;    Randomized algorithm;    Matrix completion;    Fourier integral operator;    Special function transform;   

DOI  :  10.1016/j.jcp.2019.02.044

来源: Elsevier

【 摘 要 】

This paper concerns the fast evaluation of the matvec g = Kf for K is an element of C-NxN, which is the discretization of an oscillatory integral transform g(x) = integral K(x, xi) f(xi)d xi with a kernel function K(x, xi) = alpha(x, xi)e(2 pi i Phi(x, xi)), where alpha(x, xi) is a smooth amplitude function, and Phi(x, xi) is a piecewise smooth phase function with O(1) discontinuous points in x and xi. A unified framework is proposed to compute Kf with O (N log N) time and memory complexity via the non-uniform fast Fourier transform (NUFFT) or the butterfly factorization (BF), together with an O (N) fast algorithm to determine whether NUFFT or BF is more suitable. This framework works for two cases: 1) explicit formulas for the amplitude and phase functions are known; 2) only indirect access of the amplitude and phase functions are available. Especially in the case of indirect access, our main contributions are: 1) an O (N log N) algorithm for recovering the amplitude and phase functions is proposed based on a new low-rank matrix recovery algorithm; 2) a new stable and nearly optimal BF with amplitude and phase functions in a form of a low-rank factorization (IBF-MAT(1)) is proposed to evaluate the matvec Kf. Numerical results are provided to demonstrate the effectiveness of the proposed framework. (C) 2019 Elsevier Inc. All rights reserved.

【 授权许可】

Free