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.
Finally, an earlier version of the work presented in this paper can be found in @cite_20 , in which the notion of polarized traces using Green's representation formula was first introduced, obtaining favorable scalings;
@cite_20
2019394709
In this paper we consider the localization of a collection of small, three-dimensional bounded homogeneous inclusions via time-harmonic electromagnetic means, typically using arrays of electric or magnetic dipole transmitters and receivers with given polarization(s) at some distance from the collection, possibly also lying in the far field. The inclusions, somewhat apart or closely spaced, are buried within a homogeneous medium, and are of arbitrary contrast of permittivity, conductivity, and permeability vis-ag-vis this embedding medium. The problem is formulated as an inverse scattering problem for the full Maxwell equations and it involves a robust asymptotic modeling of the multistatic response matrix. No specific application is studied at this stage, but characterization of obstacles in subsoils, nondestructive evaluation of man-made structures, and medical imaging are primary fields of application envisaged. The proposed approach uses a MUSIC (multiple signal classification)-type algorithm, and it yields fast numbering, accurate localization, and estimates of the electromagnetic and geometric parameters (polarization tensors) of the inclusions. The mathematical machinery is detailed first, some specific attention being given to triaxial ellipsoidal inclusions and degenerate spherical shapes (for the latter known results are retrieved). Then, the viability of this algorithm—which would be easily extended to planarly layered environments by introduction of their Green’s functions—is documented by a variety of numerical results from synthetic, noiseless, and severely noisy field data.