×

A new directional algebraic fast multipole method based iterative solver for the Lippmann-Schwinger equation accelerated with HODLR preconditioner. (English) Zbl 1508.65149

Summary: We present a fast iterative solver for scattering problems in 2D, where a penetrable object with compact support is considered. By representing the scattered field as a volume potential in terms of the Green’s function, we arrive at the Lippmann-Schwinger equation in integral form, which is then discretized using an appropriate quadrature technique. The discretized linear system is then solved using an iterative solver accelerated by Directional Algebraic Fast Multipole Method (DAFMM). The DAFMM presented here relies on the directional admissibility condition of the 2D Helmholtz kernel [B. Engquist and L. Ying, Commun. Math. Sci. 7, No. 2, 327–345 (2009; Zbl 1182.65178)], and the construction of low-rank factorizations of the appropriate low-rank matrix sub-blocks is based on our new Nested Cross Approximation (NCA) [V. Gujjula and S. Ambikasaran, “A new nested cross approximation”, Preprint, arXiv:2203.14832]. The advantage of the NCA described in [loc. cit.] is that the search space of so-called far-field pivots is smaller than that of the existing NCAs [Y. Zhao et al., “Fast nested cross approximation algorithm for solving large-scale electromagnetic problems”, IEEE Trans. Microwave Theory Tech. 67, No. 8, 3271–3283 (2019; doi:10.1109/TMTT.2019.2920894); M. Bebendorf and R. Venn, Numer. Math. 121, No. 4, 609–635 (2012; Zbl 1252.65206)]. Another significant contribution of this work is the use of HODLR based direct solver [S. Ambikasaran and E. Darve, J. Sci. Comput. 57, No. 3, 477–501 (2013; Zbl 1292.65030)] as a preconditioner to further accelerate the iterative solver. In one of our numerical experiments, the iterative solver does not converge without a preconditioner. We show that the HODLR preconditioner is capable of solving problems that the iterative solver can not. Another noteworthy contribution of this article is that we perform a comparative study of the HODLR based fast direct solver, DAFMM based fast iterative solver, and HODLR preconditioned DAFMM based fast iterative solver for the discretized Lippmann-Schwinger problem. To the best of our knowledge, this work is one of the first to provide a systematic study and comparison of these different solvers for various problem sizes and contrast functions. In the spirit of reproducible computational science, the implementation of the algorithms developed in this article is made available at https://github.com/vaishna77/Lippmann_Schwinger_Solver.

MSC:

65M80 Fundamental solutions, Green’s function methods, etc. for initial value and initial-boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35J08 Green’s functions for elliptic equations
65F55 Numerical methods for low-rank matrix approximation; matrix compression
65R10 Numerical methods for integral transforms
65R20 Numerical methods for integral equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Sections 6.2.5 and 6.2.9 indicate that at high values of κ (the example considered is 300), the convergence of GMRES is poor. Hence in such cases, it is advisable to either use an References
[2] B. Engquist, L. Ying et al., A fast directional algorithm for high frequency acoustic scattering in two dimensions, Communications in Mathematical Sciences 7 (2) (2009) 327-345. · Zbl 1182.65178
[3] V. Gujjula, S. Ambikasaran, A new nested cross approximation, arXiv e-prints arXiv:2203.14832 (2022).
[4] Y. Zhao, D. Jiao, J. Mao, Fast nested cross approximation algorithm for solving large-scale electromagnetic problems, IEEE Transactions on Microwave Theory and Techniques 67 (8) (2019) 3271-3283.
[5] M. Bebendorf, R. Venn, Constructing nested bases approximations from the entries of non-local operators, Numerische Mathematik, 121 (2012), pp. 609-635. · Zbl 1252.65206
[6] S. Ambikasaran, E. Darve, An O(nlogn) fast direct solver for partial hierarchically semi-separable matrices, Journal of Scientific Computing 57 (3) (2013) 477-501. · Zbl 1292.65030
[7] S. Ambikasaran, C. Borges, L.-M. Imbert-Gerard, L. Greengard, Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions, SIAM Jour-nal on Scientific Computing 38 (3) (2016) A1770-A1787. · Zbl 1416.65484
[8] V. Rokhlin, Rapid solution of integral equations of scattering theory in two dimensions, Journal of Computational Physics 86 (2) (1990) 414-439. · Zbl 0686.65079
[9] M. Messner, M. Schanz, E. Darve, Fast directional multilevel summation for oscillatory ker-nels based on Chebyshev interpolation, Journal of Computational Physics 231 (4) (2012) 1175-1196. · Zbl 1239.65002
[10] M. Bebendorf, C. Kuske, R. Venn, Wideband nested cross approximation for Helmholtz problems, Numerische Mathematik 130 (1) (2015) 1-34. · Zbl 1317.65242
[11] S. Börm, L. Grasedyck, W. Hackbusch, Introduction to hierarchical matrices with applica-tions, Engineering Analysis with Boundary Elements 27 (5) (2003) 405-422. · Zbl 1035.65042
[12] S. Börm, L. Grasedyck, W. Hackbusch, Hierarchical matrices, Lecture Notes 21 (2003) 2003.
[13] W. Hackbusch, H 2 -matrices, in: Hierarchical Matrices: Algorithms and Analysis, Springer, 2015, pp. 203-240. · Zbl 1336.65041
[14] W. Hackbusch, S. Börm, H 2 -matrix approximation of integral operators by interpolation, Applied Numerical Mathematics 43 (1-2) (2002) 129-143. · Zbl 1019.65103
[15] W. Hackbusch, B. Khoromskij, S. Sauter, On H 2 -matrices, Lectures on Applied Mathematics, 2000, pp. 9-29.
[16] S. Börm, Directional-matrix compression for high-frequency problems, Numerical Linear Algebra with Applications 24 (6) (2017) e2112. · Zbl 1474.65121
[17] M. Abramowitz, I. A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, Vol. 55, US Government printing office, 1964. · Zbl 0171.38503
[18] F. W. Olver, D. W. Lozier, R. F. Boisvert, C. W. Clark, NIST Handbook of Mathematical Func-tions Hardback and CD-ROM, Cambridge University Press, 2010. · Zbl 1198.00002
[19] Boost C++ libraries, https://www.boost.org/doc/libs/1_76_0/libs/math/doc/html/ math_toolkit/bessel/bessel_first.html, accessed: 2022-06-25.
[20] S. Rjasanow, Adaptive cross approximation of dense matrices, in: Int. Association Boundary Element Methods Conf., IABEM, 2002, pp. 28-30.
[21] K. Zhao, M. N. Vouvakis, J.-F. Lee, The adaptive cross approximation algorithm for accel-erated method of moments computations of EMC problems, IEEE Transactions on Electro-magnetic Compatibility 47 (4) (2005) 763-773.
[22] L. Greengard, The rapid evaluation of potential fields in particle systems, MIT press, 1988. · Zbl 1001.31500
[23] L. Greengard, V. Rokhlin, A fast algorithm for particle simulations, Journal of Computa-tional Physics 73 (2) (1987) 325-348. · Zbl 0629.65005
[24] W. Fong, E. Darve, The black-box fast multipole method, Journal of Computational Physics 228 (23) (2009) 8712-8725. · Zbl 1177.65009
[25] Y. Saad, M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving non-symmetric linear systems, SIAM Journal on Scientific and Statistical Computing 7 (3) (1986) 856-869. · Zbl 0599.65018
[26] Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003. · Zbl 1031.65046
[27] S. Ambikasaran, K. R. Singh, S. S. Sankaran, Hodlrlib: A library for hierarchical matrices, Journal of Open Source Software 4 (34) (2019) 1167.
[28] B. Engquist, L. Ying, Fast directional algorithms for the Helmholtz kernel, Journal of Com-putational and Applied Mathematics 234 (6) (2010) 1851-1859. · Zbl 1379.65103
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.