The high-frequency Helmholtz equation in a heterogeneous medium is a difficult problem in numerical analysis. Direct solvers are either unwieldy to set up for the problem as a whole, or are hard to link up in a domain decomposition framework. On the other hand, preconditioners for iterative solvers tend to suffer either from a lack of scalability, or from a convergence rate highly dependent on the frequency.  

In this work, we present a hybrid approach, which results in a highly scalable algorithm with sublinear runtime in the number of unknowns normally needed to represent the solution in the volume.

This approach uses efficient direct solvers locally in large subdomains and properly couples them with transmission conditions in the form of incomplete Green’s integrals. The coupling allows us to reduce the problem to a boundary integral equation, which is solved iteratively. The BIE is preconditioned by introducing a polarization of the waves thus achieving a fast convergence rate independently of the frequency and the number of subdomains. This approach is especially attractive when the local Green’s functions are precomputed, and a fast algorithm is available for their application.