text: 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.
  @cite_84: 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.
summary: 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;