arrow
Volume 32, Issue 4
A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with HODLR Preconditioner

Vaishnavi Gujjula & Sivaram Ambikasaran

Commun. Comput. Phys., 32 (2022), pp. 1061-1093.

Published online: 2022-10

Export citation
  • Abstract

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 [1], and the construction of low-rank factorizations of the appropriate low-rank matrix sub-blocks is based on our new Nested Cross Approximation (NCA) [2]. The advantage of the NCA described in [2] is that the search space of so-called far-field pivots is smaller than that of the existing NCAs [3, 4]. Another significant contribution of this work is the use of HODLR based direct solver [5] 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.

  • AMS Subject Headings

31A10, 35J05, 35J08, 65F55, 65R10, 65R20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CiCP-32-1061, author = {Gujjula , Vaishnavi and Ambikasaran , Sivaram}, title = {A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with HODLR Preconditioner}, journal = {Communications in Computational Physics}, year = {2022}, volume = {32}, number = {4}, pages = {1061--1093}, abstract = {

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 [1], and the construction of low-rank factorizations of the appropriate low-rank matrix sub-blocks is based on our new Nested Cross Approximation (NCA) [2]. The advantage of the NCA described in [2] is that the search space of so-called far-field pivots is smaller than that of the existing NCAs [3, 4]. Another significant contribution of this work is the use of HODLR based direct solver [5] 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.

}, issn = {1991-7120}, doi = {https://doi.org/10.4208/cicp.OA-2022-0103}, url = {http://global-sci.org/intro/article_detail/cicp/21139.html} }
TY - JOUR T1 - A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with HODLR Preconditioner AU - Gujjula , Vaishnavi AU - Ambikasaran , Sivaram JO - Communications in Computational Physics VL - 4 SP - 1061 EP - 1093 PY - 2022 DA - 2022/10 SN - 32 DO - http://doi.org/10.4208/cicp.OA-2022-0103 UR - https://global-sci.org/intro/article_detail/cicp/21139.html KW - Directional Algebraic Fast Multipole Method, Lippmann-Schwinger equation, low-rank matrix, Helmholtz kernel, Nested Cross Approximation, HODLR direct solver, Preconditioner. AB -

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 [1], and the construction of low-rank factorizations of the appropriate low-rank matrix sub-blocks is based on our new Nested Cross Approximation (NCA) [2]. The advantage of the NCA described in [2] is that the search space of so-called far-field pivots is smaller than that of the existing NCAs [3, 4]. Another significant contribution of this work is the use of HODLR based direct solver [5] 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.

Vaishnavi Gujjula & Sivaram Ambikasaran. (2022). A New Directional Algebraic Fast Multipole Method Based Iterative Solver for the Lippmann-Schwinger Equation Accelerated with HODLR Preconditioner. Communications in Computational Physics. 32 (4). 1061-1093. doi:10.4208/cicp.OA-2022-0103
Copy to clipboard
The citation has been copied to your clipboard