Special Seminar in Applied Mathematics

Solving the Helmholtz equation in heterogenous media at high-frequency is among the last open problems in numerical analysis for linear PDE's. There is no known procedure for solving the high-frequency Helmholtz equation in quasi-linear time for real world applications. Sparse factorizations can be prohibitively expensive, algebraic preconditioners tend to explode in complexity in the high-frequency regime, and multigrid methods scale poorly. In this talk I present a new preconditioner based on domain decomposition, integral operators and fast algorithms. The preconditioner is designed to be seamlessly integrated in a high performance computing environment. The algorithm separates the computation in two parts, one expensive, but highly parallel, and a second one, sequential but with sub-linear complexity; keeping a linear overhead of communication per solve. I will discuss the new algorithm, the supporting mathematics and some details of the implementation. Finally, I will demonstrate the sub-linear complexity numerically on examples from geophysics. Joint work with Laurent Demanet.