Multidimensional phase recovery and interpolative decomposition butterfly factorization

JOURNAL OF COMPUTATIONAL PHYSICS

卷:412

Article

Chen, Ze¹  Zhang, Juan²  Ho, Kenneth L.³  Yang, Haizhao⁴ 

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

[2] Xiangtan Univ, Dept Math & Computat Sci, Xiangtan, Peoples R China

[3] Flatiron Inst, Ctr Computat Math, New York, NY USA

[4] Purdue Univ, Dept Math, W Lafayette, IN 47907 USA

关键词: Data-sparse matrix;    Butterfly factorization;    Interpolative decomposition;    Operator compression;    Randomized algorithm;    Matrix completion;   

DOI  :  10.1016/j.jcp.2020.109427

来源: Elsevier

【 摘 要 】

This paper focuses on the fast evaluation of the matrix-vector multiplication (matvec) g= Kf for K is an element of C-NxN, which is the discretization of a multidimensional oscillatory integral transform g(x) = similar to K(x,xi) f(xi)d xi with a kernel function K(x, xi) = e(2 pi i Phi(x,xi)), where Phi(x, xi) is a piecewise smooth phase function with x and xi in R-d for d = 2 or 3. A new framework is introduced to compute Kfwith O ( Nlog(N)) time and memories complexity in the case that only indirect access to the phase function Phi is available. This framework consists of two main steps: 1) an O (Nlog(N)) algorithm for recovering the multidimensional phase function Phi from indirect access is proposed; 2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec Kfwith an O (Nlog( N)) complexity once Phi is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free