Fast Alternating BiDirectional Preconditioner for the 2D High-Frequency Lippmann--Schwinger Equation
Leonardo Zepeda-Núñez, Hongkai Zhao · SIAM Journal on Scientific Computing · 2016
This paper presents a fast iterative solver for the Lippmann--Schwinger equation for high-frequency waves scattered by a smooth medium with a compactly supported inhomogeneity. The solver is based on the sparsifying preconditioner [L. Ying, Multiscale Model. Simul., 13 (2015), pp. 644--660] and a domain decomposition approach similar to the method of polarized traces [L. Zepeda-Nún͂ez and L. Demanet, J. Comput. Phys., 308 (2016), pp. 347--388.] The iterative solver has two levels, the outer level in which a sparsifying preconditioner for the Lippmann--Schwinger equation is constructed, and the inner level, in which the resulting sparsified system is solved quickly using an iterative solver preconditioned with a bidirectional matrix-free variant of the method of polarized traces. The complexity of the construction and application of the preconditioner is ${\cal O}(N)$ and ${\cal O}(N\log{N})$, respectively, where $N$ is the number of degrees of freedom. Numerical experiments in 2 dimensions indicate that the number of iterations in both levels depends weakly on the frequency resulting in a method with an overall ${\cal O}(N\log{N})$ complexity.