Multidimensional phase recovery and interpolative decomposition butterfly factorization
Multidimensional phase recovery and interpolative decomposition butterfly factorization
复制标题
多维相位恢复和插值分解蝴蝶分解
DOI：
10.1016/j.jcp.2020.109427
复制
发表时间：
2019-08
影响因子：
4.1
通讯作者：
Yang Haizhao
中科院分区：
文献类型：
--
作者：
Chen Ze;Zhang Juan;Ho Kenneth L.;Yang Haizhao
本文主要研究矩阵向量乘法（matvec）g= Kf（K∈ CN × N）的快速计算，它是多维振荡积分变换g（x）=<$K（x，<$）f（<$）d <$$>的离散化，其核函数为K（x，<$）= e2 π i Φ（x，<$），其中Φ（x，是分段光滑相位函数，其中x和λ在R d中，d= 2或3。在只能间接访问相位函数Φ的情况下，提出了一种新的计算Kf的框架，其时间和内存复杂度为O（NlogN（N））.该框架由两个主要步骤组成：1）提出了一个O（Nlog（N））的从间接访问中恢复多维相位函数Φ的算法; 2）设计了一个多维插值分解蝴蝶因子分解（MIDBF），一旦Φ可用，则以O（Nlog（N））的复杂度计算矩阵Kf。数值结果证明了所提出的框架的有效性。
This paper focuses on the fast evaluation of the matrix-vector multiplication (matvec) g= K f for K∈ C N× N, which is the discretization of a multidimensional oscillatory integral transform g (x)=∫ K (x, ξ) f (ξ) d ξ with a kernel function K (x, ξ)= e 2 π i Φ (x, ξ), where Φ (x, ξ) is a piecewise smooth phase function with x and ξ in R d for d= 2 or 3. A new framework is introduced to compute Kf with O (N log(N)) time and memories complexity in the case that only indirect access to the phase function Φ is available. This framework consists of two main steps: 1) an O (N log(N)) algorithm for recovering the multidimensional phase function Φ from indirect access is proposed; 2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec Kf with an O (N log(N)) complexity once Φ is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework.
登录
查看更多内容
DOI：
10.1109/36.739085
发表时间：
1999
期刊：
IEEE Trans. Geosci. Remote. Sens.
影响因子：
--
作者：
M. Costantini;A. Farina;F. Zirilli
通讯作者：
M. Costantini;A. Farina;F. Zirilli
DOI：
10.1007/978-0-387-89498-0_2
发表时间：
2009
期刊：
--
影响因子：
--
作者：
E. Pan
通讯作者：
E. Pan
DOI：
10.1137/0908079
发表时间：
1987-11
期刊：
Siam Journal on Scientific and Statistical Computing
影响因子：
--
作者：
P. Hoffman;K. Reddy
通讯作者：
P. Hoffman;K. Reddy
DOI：
10.1145/1944345.1944347
发表时间：
2009-10
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
K. Buchin;Wolfgang Mulzer
通讯作者：
K. Buchin;Wolfgang Mulzer
DOI：
10.1090/s0025-5718-2012-02557-9
发表时间：
2012-09
期刊：
Math. Comput.
影响因子：
--
作者：
L. Demanet;Lexing Ying
通讯作者：
L. Demanet;Lexing Ying