The method of polarized traces for the 2D Helmholtz equation
详细信息 查看全文
- 作者：Leonardo Zepeda-Nú ; ñ ; ez ; lzepeda@math.mit.edu" class="auth_mail" title="E-mail the corresponding author ; Laurent Demanet
- 关键词：Domain decomposition ; Helmholtz equation ; Integral equations ; High-frequency ; Fast methods
- 刊名：Journal of Computational Physics
- 出版年：2016
- 出版时间：1 March 2016
- 年：2016
- 卷：308
- 期：Complete
- 页码：347-388
- 全文大小：3253 K
文摘
We present a solver for the 2D high-frequency Helmholtz equation in heterogeneous acoustic media, with online parallel complexity that scales optimally as user=111111111&_pii=S0021999115007809&_rdoc=1&_issn=00219991&md5=536f7f39f13ebc0c6fc82c3965b3a2ac">
, where N is the number of volume unknowns, and L is the number of processors, as long as L grows at most like a small fractional power of N. The solver decomposes the domain into layers, and uses transmission conditions in boundary integral form to explicitly define “polarized traces”, i.e., up- and down-going waves sampled at interfaces. Local direct solvers are used in each layer to precompute traces of local Green's functions in an embarrassingly parallel way (the offline part), and incomplete Green's formulas are used to propagate interface data in a sweeping fashion, as a preconditioner inside a GMRES loop (the online part). Adaptive low-rank partitioning of the integral kernels is used to speed up their application to interface data. The method uses second-order finite differences. The complexity scalings are empirical but motivated by an analysis of ranks of off-diagonal blocks of oscillatory integrals. They continue to hold in the context of standard geophysical community models such as BP and Marmousi 2, where convergence occurs in 5 to 10 GMRES iterations. While the parallelism in this paper stems from decomposing the domain, we do not explore the alternative of parallelizing the systems solves with distributed linear algebra routines.
, where N is the number of volume unknowns, and L is the number of processors, as long as L grows at most like a small fractional power of N. The solver decomposes the domain into layers, and uses transmission conditions in boundary integral form to explicitly define “polarized traces”, i.e., up- and down-going waves sampled at interfaces. Local direct solvers are used in each layer to precompute traces of local Green's functions in an embarrassingly parallel way (the offline part), and incomplete Green's formulas are used to propagate interface data in a sweeping fashion, as a preconditioner inside a GMRES loop (the online part). Adaptive low-rank partitioning of the integral kernels is used to speed up their application to interface data. The method uses second-order finite differences. The complexity scalings are empirical but motivated by an analysis of ranks of off-diagonal blocks of oscillatory integrals. They continue to hold in the context of standard geophysical community models such as BP and Marmousi 2, where convergence occurs in 5 to 10 GMRES iterations. While the parallelism in this paper stems from decomposing the domain, we do not explore the alternative of parallelizing the systems solves with distributed linear algebra routines.