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.
proposed the multi-trace formulation @cite_84 , which involves solving an integral equation posed on the interfaces of a decomposed domain, which is naturally well suited for operator preconditionning in the case of piece-wise constant medium;
@cite_84
2083690159
We present a novel boundary integral formulation of the Helmholtz transmission problem for bounded composite scatterers (that is, piecewise constant material parameters in "subdomains") that directly lends itself to operator preconditioning via Calderon projectors. The method relies on local traces on subdomains and weak enforcement of transmission conditions. The variational formulation is set in Cartesian products of standard Dirichlet and special Neumann trace spaces for which restriction and extension by zero are well defined. In particular, the Neumann trace spaces over each subdomain boundary are built as piecewise @math -distributions over each associated interface. Through the use of interior Calderon projectors, the problem is cast in variational Galerkin form with an operator matrix whose diagonal is composed of block boundary integral operators associated with the subdomains. We show existence and uniqueness of solutions based on an extension of Lions' projection lemma for non-closed subspaces. We also investigate asymptotic quasi-optimality of conforming boundary element Galerkin discretization. Numerical experiments in 2-D confirm the efficacy of the method and a performance matching that of another widely used boundary element discretization. They also demonstrate its amenability to different types of preconditioning. We study a high order Discontinuous Galerkin Time Domain (DGTD) method for solving the system of Maxwell equations. This method is formulated on a non-conforming multi-element mesh mixing an unstructured triangulation for the discretization of irregularly shaped objects with a structured (Cartesian) quadrangulation for the rest of the computational domain. Within each element, the electromagnetic field components are approximated by a high order nodal polynomial. The DG method proposed here makes use of a centered scheme for the definition of the numerical traces of the electric and magnetic fields at element interfaces, associated to a second order or fourth order leap-frog scheme for the time integration of the associated semi-discrete equations. We formulate this DGTD method in 3D and study its theoretical properties. In particular, an a priori convergence estimation is elaborated. Finally, we present numerical results for the application of the method to 2D test problems. We propose and study a domain decomposition method for solving the truncated perfectly matched layer (PML) approximation in bounded domain of Helmholtz scattering problems. The method is based on the decomposition of the domain into nonoverlapping layers and the idea of source transfer which transfers the sources equivalently layer by layer so that the solution in the final layer can be solved using a PML method defined locally outside the last two layers. The convergence of the method is proved for the case of constant wave number based on the analysis of the fundamental solution of the PML equation. The method can be used as an efficient preconditioner in the preconditioned GMRES method for solving discrete Helmholtz equations with constant and heterogeneous wave numbers. Numerical examples are included. A preconditioned iterative solver for the 3D frequency-domain wave equation applied to seismic problems is evaluated. The preconditioner corresponds to an approximate inverse of a heavily damped wave equation deduced from the (undamped) wave equation. The approximate inverse is computed with one multigrid cycle. Numerical results show that the method is robust and that the number of iterations increases roughly linearly with frequency when the grid spacing is adapted to keep a constant number of discretization points per wavelength. To evaluate the relevance of this iterative solver, the number of floating-point operations required for two imaging problems are roughly evaluated. This rough estimate indicates that the time-domain migration approach is more than one order of magnitude faster. The full-wave-form tomography, based on a least-squares formulation and a scale separation approach, has the same complexity in both domains.