×

Sparsify and sweep: an efficient preconditioner for the Lippmann-Schwinger equation. (English) Zbl 1392.65035

Summary: This paper presents an efficient preconditioner for the Lippmann-Schwinger equation that combines the ideas of the sparsifying and the sweeping preconditioners. Following first the idea of the sparsifying preconditioner, this new preconditioner starts by transforming the dense linear system of the Lippmann-Schwinger equation into a nearly sparse system. The key novelty is a newly designed perfectly matched layer (PML) stencil for the boundary degrees of freedoms. The resulting sparse system gives rise to fairly accurate solutions and hence can be viewed as an accurate discretization of the Helmholtz equation. This new PML stencil also paves the way for applying the moving PML sweeping preconditioner to invert the resulting sparse system approximately. When combined with the standard GMRES solver, this new preconditioner for the Lippmann-Schwinger equation takes only a few iterations to converge for both two-dimensional and three-dimensional (3D) problems, where the iteration numbers are almost independent of the frequency. To the best of our knowledge, this is the first method that achieves near-linear cost to solve the 3D Lippmann-Schwinger equation in high-frequency cases.

MSC:

65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65R20 Numerical methods for integral equations
78A45 Diffraction, scattering

Software:

clique; PSP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Ambikasaran, C. Borges, L.-M. Imbert-Gerard, and L. Greengard, {\it Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions}, SIAM J. Sci. Comput., 38 (2016), pp. A1770-A1787, . · Zbl 1416.65484
[2] F. Andersson and A. Holst, {\it A fast, bandlimited solver for scattering problems in inhomogeneous media}, J. Fourier Anal. Appl., 11 (2005), pp. 471-487, . · Zbl 1357.35093
[3] S. Asvadurov, V. Druskin, M. N. Guddati, and L. Knizhnerman, {\it On optimal finite-difference approximation of PML}, SIAM J. Numer. Anal., 41 (2003), pp. 287-305. · Zbl 1047.65063
[4] I. M. Babuška and S. A. Sauter, {\it Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?}, SIAM J. Numer. Anal., 34 (1997), pp. 2392-2423, . · Zbl 0894.65050
[5] I. BabuÅ¡ka, F. Ihlenburg, E. T. Paik, and S. A. Sauter, {\it A generalized finite element method for solving the Helmholtz equation in two dimensions with minimal pollution}, Comput. Methods Appl. Mecha. Engrg., 128 (1995), pp. 325-359, . · Zbl 0863.73055
[6] J.-P. Berenger, {\it A perfectly matched layer for the absorption of electromagnetic waves}, J. Comput. Phys., 114 (1994), pp. 185-200, . · Zbl 0814.65129
[7] O. P. Bruno and E. Hyde, {\it An efficient, preconditioned, high-order solver for scattering by two-dimensional inhomogeneous media}, J. Comput. Phys., 200 (2004), pp. 670-694, . · Zbl 1115.65390
[8] Y. Chen, {\it A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions}, Adv. Comput. Math., 16 (2002), pp. 175-190, . · Zbl 0993.65137
[9] Z. Chen and X. Xiang, {\it A source transfer domain decomposition method for Helmholtz equations in unbounded domain}, SIAM J. Numer. Anal., 51 (2013), pp. 2331-2356, . · Zbl 1285.65082
[10] Z. Chen and X. Xiang, {\it A source transfer domain decomposition method for Helmholtz equations in unbounded domain Part II: Extensions}, Numer. Math. Theory Methods Appl., 6 (2013), pp. 538-555. · Zbl 1299.65287
[11] W. C. Chew and W. H. Weedon, {\it A 3D perfectly matched medium from modified Maxwell’s equations with stretched coordinates}, Microw. Opt. Tech. Lett., 7 (1994), pp. 599-604, .
[12] R. Duan and V. Rokhlin, {\it High-order quadratures for the solution of scattering problems in two dimensions}, J. Comput. Phys., 228 (2009), pp. 2152-2174, . · Zbl 1161.65358
[13] B. Engquist and L. Ying, {\it Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation}, Commun. Pure Appl. Math., 64 (2011), pp. 697-735, . · Zbl 1229.35037
[14] B. Engquist and L. Ying, {\it Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers}, Multiscale Model. Simul., 9 (2011), pp. 686-710, . · Zbl 1228.65234
[15] A. George, {\it Nested dissection of a regular finite element mesh}, SIAM J. Numer. Anal., 10 (1973), pp. 345-363. Collection of articles dedicated to the memory of George E. Forsythe. · Zbl 0259.65087
[16] S. G. Johnson, {\it Notes on Perfectly Matched Layers (PMLs)}, Lecture notes, Massachusetts Institute of Technology, Cambridge, MA, 2008.
[17] J. Kristek, P. Moczo, and M. Galis, {\it A brief summary of some PML formulations and discretizations for the velocity-stress equation of seismic motion}, Stud. Geophys. Geodaetica, 53 (2009), p. 459. · Zbl 1317.86001
[18] F. Lanzara, V. Maz’ya, and G. Schmidt, {\it Numerical solution of the Lippmann-Schwinger equation by approximate approximations}, J. Fourier Anal. Appl., 10 (2004), pp. 645-660, . · Zbl 1174.65556
[19] F. Liu and L. Ying, {\it Additive sweeping preconditioner for the Helmholtz equation}, Multiscale Model. Simul., 14 (2016), pp. 799-822. · Zbl 1338.65077
[20] F. Liu and L. Ying, {\it Recursive sweeping preconditioner for the three-dimensional Helmholtz Equation}, SIAM J. Sci. Comput., 38 (2016), pp. A814-A832, . · Zbl 1376.65035
[21] F. Liu and L. Ying, {\it Localized sparsifying preconditioner for periodic indefinite systems}, Commun. Math. Sci., 15 (2017), pp. 1155-1169, . · Zbl 1369.65153
[22] J. Lu and L. Ying, {\it Sparsifying preconditioner for soliton calculations}, J. Comput. Phys., 315 (2016), pp. 458-466, . · Zbl 1349.65606
[23] J. Poulson, B. Engquist, S. Li, and L. Ying, {\it A parallel sweeping preconditioner for heterogeneous} 3{\it D Helmholtz equations}, SIAM J. Sci. Comput., 35 (2013), pp. C194-C212. · Zbl 1275.65073
[24] J. Sifuentes, {\it Preconditioned Iterative Methods for Inhomogeneous Acoustic Scattering Applications}, Ph.D. thesis, Rice University, Houston, TX, 2010.
[25] C. C. Stolk, {\it A rapidly converging domain decomposition method for the Helmholtz equation}, J. Comput. Phys., 241 (2013), pp. 240-252, . · Zbl 1349.65426
[26] C. C. Stolk, {\it A dispersion minimizing scheme for the} 3-{\it D Helmholtz equation based on ray theory}, J. Comput. Phys., 314 (2016), pp. 618-646, , . · Zbl 1349.65571
[27] G. Vainikko, {\it Fast solvers of the Lippmann-Schwinger equation}, in Direct and Inverse Problems of Mathematical Physics, Springer, Berlin, 2000, pp. 423-440. · Zbl 0962.65097
[28] F. Vico, L. Greengard, and M. Ferrando, {\it Fast convolution with free-space Green’s functions}, J. Comput. Phys., 323 (2016), pp. 191-203, , . · Zbl 1415.65269
[29] A. Vion and C. Geuzaine, {\it Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem}, J. Comput. Phys., 266 (2014), pp. 171-190. · Zbl 1296.65169
[30] L. Ying, {\it Sparsifying preconditioner for pseudospectral approximations of indefinite systems on periodic structures}, Multiscale Model. Simul., 13 (2015), pp. 459-471, . · Zbl 1317.65086
[31] L. Ying, {\it Sparsifying preconditioner for the Lippmann-Schwinger equation}, Multiscale Model. Simul., 13 (2015), pp. 644-660, . · Zbl 1317.65087
[32] L. Zepeda-Nún͂ez and L. Demanet, {\it The method of polarized traces for the} 2{\it D Helmholtz equation}, J. Comput. Phys., 308 (2016), pp. 347-388, . · Zbl 1351.76197
[33] L. Zepeda-Nún͂ez and H. Zhao, {\it Fast alternating bidirectional preconditioner for the} 2D {\it high-frequency Lippmann-Schwinger equation}, SIAM J. Sci. Comput., 38 (2016), pp. B866-B888, .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.