We present a solver for the 2D high-frequency Helmholtz equation in heterogeneous acoustic media, with online parallel complexity that scales optimally as @math , where @math is the number of volume unknowns, and @math is the number of processors, as long as @math grows at most like a small fractional power of @math . 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.
, developped an additive Schwarz iteration coupled with coarse grid preconditioner based on an eigenvalue decomposition of the DtN maps inside each subdomain @cite_72 ;
@cite_72
2164119610
A new domain decomposition method is presented for the exterior Helmholtz problem. The nonlocal Dirichlet-to-Neumann (DtN) map is used as a nonreflecting condition on the outer computational boundary. The computational domain is divided into nonoverlapping subdomains with Sommerfeld-type conditions on the adjacent subdomain boundaries to ensure uniqueness. An iterative scheme is developed, where independent subdomain boundary-value problems are obtained by applying the DtN operator to values from the previous iteration. The independent problems are then discretized with finite elements and can be solved concurrently. Numerical results are presented for a two-dimensional model problem, and both the solution accuracy and convergence rate are investigated.