betaFeedback

WorksMathematics

A Hierarchical direct solver for Lippmann-Schwinger equations based on boundary traces

Abstract

A high-order hierarchical direct solver for variable-media scattering in two dimensions is presented. Standard discretizations for these problems produce dense linear systems that are commonly solved iteratively, requiring a new global solve for each incident field. The method proposed here instead constructs a reusable scattering operator for the inhomogeneous medium, based on a hierarchical subdivision of the computational domain. First, high-accuracy leaf scattering operators are built from discretized local integral equations. Up the hierarchy, neighboring boxes are merged to build the scattering operators for successively larger boxes. A key feature of the method is that each scattering operator is represented as a map of incoming traces to outgoing traces. Consequently, volume unknowns appear only in the leaf computations; all higher levels of the hierarchy operate entirely on boundary traces. The hierarchical solver is presented first at the continuum level and discretized only afterward using high-order local volume quadrature, polynomial trace representations, and boundary integral techniques. For a discretization involving NN degrees of freedom, the method requires O(N3/2)O(N^{3/2}) work and O(Nlog⁡N)O(N\log N) storage to build all scattering operators. Once these are available, any incoming field can be processed at cost O(N)O(N) if only the outgoing field is required, and cost O(Nlog⁡N)O(N\log N) if the full field is required. Numerical experiments demonstrate high-order accuracy on a range of challenging scattering problems including cavities, back-scattering, limited regularity, and high wavenumber, that pose significant challenges to iterative methods.

Introduction

This paper describes a method for numerically solving a variable coefficient Helmholtz equation of the form

{−Δu(x)−κ2(1−b(x))u(x)=−κ2b(x)uin(x),for x∈R2,∂u(x)∂r−iκu(x)=o(r−1/2),as r:=∣x∣→∞.(1)\begin{cases} -\Delta u(\boldsymbol{x})-\kappa^2(1-b(\boldsymbol{x}))u(\boldsymbol{x})=-\kappa^2b(\boldsymbol{x})u_{\mathrm{in}}(\boldsymbol{x}), & \text{for }\boldsymbol{x}\in\mathbb{R}^2,\\ \frac{\partial u(\boldsymbol{x})}{\partial r}-\mathrm{i}\kappa u(\boldsymbol{x})=o(r^{-1/2}), & \text{as }r:=|\boldsymbol{x}|\to\infty. \tag*{(1)} \end{cases}

Here κ∈R\kappa\in\mathbb{R} is the wave-number, uinu_{\mathrm{in}} is a prescribed incoming field satisfying the free-space Helmholtz equation in a neighborhood of the scatterer, and bb is a compactly supported scattering potential. We let Ω\Omega denote a rectangular domain that encloses the support of bb, and further assume for simplicity that uinu_{\mathrm{in}} satisfies the free-space Helmholtz equation throughout Ω\Omega. When b(x)<1b(\boldsymbol{x})<1, an acoustic interpretation is obtained by relating bb to the local wave speed v(x)v(\boldsymbol{x}) and the free-space value vfreev_{\mathrm{free}} through

b(x)=1−(vfreev(x))2.b(\boldsymbol{x})=1-\left(\frac{v_{\mathrm{free}}}{v(\boldsymbol{x})}\right)^2.

The scattered field uu is required to satisfy the Sommerfeld radiation condition. Figure 1 illustrates the geometry.

Figure 1. Geometry of the scattering problem. Waves propagate in a medium with constant wave speed vfreev_{\mathrm{free}} everywhere except in the shaded areas, where the wave speed is given by v(x)=vfree/1−b(x)v(\boldsymbol{x}) = v_{\mathrm{free}/\sqrt{1-b(\boldsymbol{x})}}, with b=b(x)b = b(\boldsymbol{x}) a given, smooth, compactly supported “scattering potential.” An incident field uinu_{\mathrm{in}} hits the scattering potential and induces the scattered field uu. The dashed line marks the artificial domain Ω\Omega, which encloses the support of the scattering potential.

A particularly attractive formulation of (1) is obtained by introducing the free-space fundamental solution

Gκ(x,y)=i4H0(1)(κ∣x−y∣),G_\kappa(\boldsymbol{x},\boldsymbol{y}) = \frac{i}{4} H_0^{(1)}(\kappa|\boldsymbol{x}-\boldsymbol{y}|),

where H0(1)H_0^{(1)} is the Hankel function of the first kind of order zero. This is the outgoing free-space fundamental solution for −Δ−κ2I-\Delta-\kappa^2 I. We then write

u(x)=∫ΩGκ(x,y)q(y) dy,x∈R2.(2)u(\boldsymbol{x}) = \int_{\Omega} G_\kappa(\boldsymbol{x},\boldsymbol{y})q(\boldsymbol{y})\,d\boldsymbol{y}, \qquad\boldsymbol{x} \in\mathbb{R}^2. \tag*{(2)}

The source density qq then satisfies the Lippmann–Schwinger equation

q(x)+κ2b(x)∫ΩGκ(x,y)q(y) dy=−κ2b(x)uin(x),x∈Ω.(3)q(\boldsymbol{x})+\kappa^2b(\boldsymbol{x})\int_{\Omega}G_\kappa(\boldsymbol{x},\boldsymbol{y})q(\boldsymbol{y})\,d\boldsymbol{y}=-\kappa^2b(\boldsymbol{x})u_{\mathrm{in}}(\boldsymbol{x}), \qquad\boldsymbol{x}\in\Omega. \tag*{(3)}

The formulation (3) has several well-known advantages: the computational domain is finite, the radiation condition is enforced automatically, and the equation has the structure of a Fredholm equation of the second kind [12]. High-order discretizations are available for smooth media [1, 15, 2], with related high-order volume-integral discretizations also developed for more general acoustic and electromagnetic media [3, 7].

The main computational drawback is that a discretization of (3) produces a dense linear system involving all degrees of freedom in the scattering region. A standard approach to overcome this problem is to deploy an iterative solver, where each application of the operator is accelerated using a fast method such as the FFT or the Fast Multipole Method [1, 15]. Considerable work has been devoted to making such iterations effective at high frequency and for strongly scattering media, including sparsifying and sweeping preconditioners [37, 39, 28, 22]. For many problems these techniques are highly effective and are the natural methods of choice. There remain, however, important regimes in which the global iteration can be difficult, and applications involving many incoming fields require repeated solution of essentially the same scattering problem. These considerations motivate the construction of a reusable direct solver.

The method developed in this paper is based on a simple observation. Consider any square or rectangular subdomain Ωτ\Omega_\tau. The field incident on Ωτ\Omega_\tau from sources outside the box satisfies the homogeneous Helmholtz equation inside the box, while the field generated by sources inside Ωτ\Omega_\tau satisfies the homogeneous Helmholtz equation outside it. We represent both fields by their traces on the boundary Γτ=∂Ωτ\Gamma_\tau=\partial\Omega_\tau. The response of the entire volume Ωτ\Omega_\tau can then be summarized by a boundary-to-boundary scattering operator

Fτ:{incoming trace on Γτ}⟼{outgoing trace on Γτ}.F^\tau:\quad\{\text{incoming trace on }\Gamma_\tau\}\longmapsto\{\text{outgoing trace on }\Gamma_\tau\}.

Once FτF^\tau has been constructed, the volume degrees of freedom inside Ωτ\Omega_\tau no longer need to participate in interactions with the rest of the problem.

The method is hierarchical. The computational domain is first partitioned into a collection of small leaf boxes, which are organized into a binary tree by recursively pairing neighboring boxes. Each parent box is the union of its two children, and the root of the tree is the full computational domain Ω\Omega. On each leaf, a scattering operator is constructed by solving local Lippmann–Schwinger problems in the volume. The scattering operators are then merged pairwise in an upward pass through the tree: given the scattering operators of two children, a boundary-only calculation produces the scattering operator of their parent. Repeating this process yields a scattering operator for the entire inhomogeneous medium.

A key feature of the method is that volume unknowns appear only in the leaf computations. At all higher levels, the hierarchy operates entirely on boundary traces. This dimensional reduction is particularly attractive at high accuracy, since inter-box interactions are represented directly by high-order boundary fields rather than by increasingly rich subsets of a volume discretization.

The method naturally separates into three computational stages. First, a set of geometry- and frequency-dependent Helmholtz continuation and evaluation operators is constructed. These operators depend only on the box sizes and on the wave-number κ\kappa, not on the scattering potential, and can therefore be precomputed and reused for different media. Second, once the medium bb is specified, local scattering operators are built and merged in an upward pass. Third, after this build stage, each new incoming field can be processed rapidly through the stored hierarchy.

For a discretization with NN degrees of freedom, the method requires O(N3/2)O(N^{3/2}) work to construct the hierarchical scattering representation. Retaining the operators needed for subsequent recovery of the full volume solution requires O(Nlog⁡N)O(N \log N) storage, while a variant that constructs only the root scattering operator requires only O(N)O(N) storage. Once the hierarchy has been built, new incident fields can be processed without any further volume solves. (Let us note that the matrices representing the scattering operators FtF^t appear to have internal rank structure that could in principle be exploited to further reduce asymptotic complexities, see Remark 4.)

In this work, the reduction to boundary traces and the hierarchical structure of scattering operators are derived at the continuum level, before discretization. To realize the resulting algorithm numerically, we use high-order discretizations of the local Lippmann–Schwinger equation and high-order polynomial representations of the boundary traces (with p=10p = 10 or p=20p = 20 being representative). The continuation and evaluation operators are constructed using standard high-order boundary integral equation techniques.

The present approach is related to several existing lines of work. Fast iterative methods for the Lippmann–Schwinger equation form the main computational baseline [1, 15, 37, 39, 28]. Hierarchical construction of scattering operators for volume integral equations has important precedents, notably the work of Chen [8]. T-matrix and multiple-scattering methods likewise characterize individual scatterers by maps from incident to scattered fields [17, 19, 18]. There is also a substantial literature on direct solvers that first discretize the volume integral equation and then exploit rank structure in the resulting dense matrix [2, 14]. A particularly close predecessor is the direct solver of [22], which likewise uses a hierarchical construction based on scattering operators for the Lippmann–Schwinger equation. In [22], the volume integral equation is first discretized, and rank structure in the resulting dense matrix is then exploited to construct and merge discrete scattering operators. The present construction reverses the order of these operations: the hierarchical reduction is formulated at the continuum level, so that all inter-box interactions above the leaf level are represented directly by boundary traces, with discretization introduced only afterward. This distinction becomes particularly important in the high-accuracy regime, where the interaction ranks in the discrete formulation of [22] can become large.

The organization of the present method is reminiscent of hierarchical Poincaré–Steklov (HPS) solvers for differential equations [29, 20]: local problems are condensed into boundary response operators and these are merged recursively. The distinction is that the local variable-coefficient scattering problems here are solved through the Lippmann–Schwinger equation rather than by directly discretizing the differential operator.

The contribution of this paper is a high-order numerical realization of this field-to-field hierarchical scattering construction. We give the exact continuum merge identities, describe a practical discretization based on high-order local volume solves and boundary traces, and present numerical experiments on a range of variable-media scattering problems. The present implementation deliberately does not exploit the substantial numerical rank structure that appears in many of the merge operators; this provides an immediate avenue for future acceleration.

The remainder of the paper is organized as follows. § 2 defines the local incoming and outgoing fields and the field-to-field scattering operator. § 3 derives the merge operation, first for separated scatterers and then for adjacent boxes. § 4 describes the complete hierarchical continuum algorithm, including the downward recovery of the interior solution. § 5 describes the discretization and implementation. Numerical experiments are presented in § 6, and conclusions are given in § 7.

Local scattering operators

In this section, we give a precise mathematical definition of the local scattering operators that will serve as the basic building blocks of our hierarchical solver. Throughout this section, τ\tau denotes a label associated with a square or rectangular subdomain Ωτ⊂Ω\Omega_\tau\subset\Omega, with boundary Γτ=∂Ωτ\Gamma_\tau= \partial\Omega_\tau, cf. Figure 2. These subdomains will later form part of the hierarchical tree.

Figure 2. A box Ωτ\Omega_\tau contains the support of a scattering potential bb. An incoming field vτv_\tau induces the scattered field wτw_\tau. The fields are represented by their traces ϕτ\phi_\tau and ψτ\psi_\tau on the artificial boundary Γτ=∂Ωτ\Gamma_\tau= \partial\Omega_\tau, so the local scattering operator FτF^\tau maps ψτ=Fτϕτ\psi_\tau= F^\tau\phi_\tau.

For a single square or rectangular subdomain, we first identify the incoming and outgoing fields, then represent these fields by their boundary traces, and finally show how the resulting boundary-to-boundary scattering operator can be constructed from a local Lippmann–Schwinger solve.

Incoming and outgoing fields

For a box Ωτ\Omega_\tau, we define incoming and outgoing fields, following standard practice. Let qq denote the solution to (3). The outgoing field generated by the sources in Ωτ\Omega_\tau is

wτ(x)=∫ΩτGκ(x,y)q(y) dy,x∈R2∖Ωτ‾.(4)w_\tau(\mathbf{x}) = \int_{\Omega_\tau} G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,\mathrm{d}\mathbf{y}, \qquad\mathbf{x} \in\mathbb{R}^{2} \setminus\overline{\Omega_\tau}. \tag*{(4)}

In other words, wτw_\tau is the radiating solution to the κ\kappa-Helmholtz equation generated by the sources inside Ωτ\Omega_\tau.

The incoming field for the box τ\tau is the sum of the externally applied field uinu_{\mathrm{in}} and the field generated by all sources outside Ωτ\Omega_\tau. Thus,

vτ(x)=uin(x)+∫Ω∖ΩτGκ(x,y)q(y) dy,x∈Ωτ.(5)v_\tau(\mathbf{x}) = u_{\mathrm{in}}(\mathbf{x}) + \int_{\Omega\setminus\Omega_\tau} G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,\mathrm{d}\mathbf{y}, \qquad\mathbf{x} \in\Omega_\tau. \tag*{(5)}

Observe that vτv_\tau satisfies the homogeneous Helmholtz equation throughout Ωτ\Omega_\tau.

Once the incoming field vτv_\tau is known, the Lippmann–Schwinger equation can be solved locally on Ωτ\Omega_\tau. Indeed, restricting (3) to Ωτ\Omega_\tau and splitting the volume potential into an interior and an exterior part gives

q(x)+κ2b(x)∫ΩτGκ(x,y)q(y) dy=−κ2b(x)vτ(x),x∈Ωτ.(6)q(\mathbf{x}) + \kappa^{2}b(\mathbf{x})\int_{\Omega_\tau} G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,\mathrm{d}\mathbf{y} = -\kappa^{2}b(\mathbf{x})v_\tau(\mathbf{x}), \qquad\mathbf{x} \in\Omega_\tau. \tag*{(6)}

Solving (6) specifies the restriction of qq to Ωτ\Omega_\tau, and hence the outgoing field wτw_\tau via (4).

Trace representations

When a scattering operator is to be computed in practice, one must specify how the incoming and outgoing fields are represented. Standard practice in the physics literature is to use truncated expansions in cylindrical harmonics (and, in three dimensions, spherical harmonics). We will instead represent both fields through their boundary traces, by which we simply mean their restrictions to the boundary. For a box τ\tau, define

ϕτ=vτ∣Γτ,ψτ=wτ∣Γτ.(7)\phi_\tau= v_\tau|_{\Gamma_\tau}, \qquad\psi_\tau= w_\tau|_{\Gamma_\tau}. \tag*{(7)}

Thus, ϕτ\phi_\tau is the incoming trace and ψτ\psi_\tau is the outgoing trace. (The incoming and outgoing fields considered here are continuous, so the boundary traces are well defined.)

The outgoing trace ψτ\psi_\tau always uniquely determines wτw_\tau: it supplies Dirichlet data for the exterior Helmholtz problem, which is uniquely solvable when coupled with the radiation condition at infinity. The incoming trace ϕτ\phi_\tau supplies Dirichlet data for an interior Helmholtz problem on Ωτ\Omega_\tau. For Helmholtz, this problem can in principle be ill-posed. For the present development, make the assumption:

For every box Ωτ\Omega_\tau in the hierarchy, the local Dirichlet problem is well posed.

Under this assumption, ϕτ\phi_\tau uniquely determines the incoming field vτv_\tau throughout Ωτ\Omega_\tau.2

We now define the boundary-to-boundary scattering operator FτF^\tau by

Fτ:ϕτ↦ψτ.(8)F^\tau: \phi_\tau\mapsto\psi_\tau. \tag*{(8)}

The scattering operator encodes the complete response of the material in Ωτ\Omega_\tau to any incoming field that is homogeneous Helmholtz in that box.

Constructing a local scattering operator

The scattering operator for a leaf box can be written as a composition of four continuum operators. Let

  • SτS_\tau be the solution operator for the local Dirichlet Helmholtz problem on Ωτ\Omega_\tau, so that

vτ=Sτϕτ.v_\tau= S_\tau\phi_\tau.
  • BτB_\tau be multiplication by the function −κ2b(x)-\kappa^2 b(\mathbf{x}).

  • LτL_\tau be the locally restricted Lippmann–Schwinger operator

[Lτq](x)=q(x)+κ2b(x)∫ΩτGκ(x,y)q(y) dy,x∈Ωτ.[L_\tau q](\mathbf{x}) = q(\mathbf{x}) + \kappa^2 b(\mathbf{x}) \int_{\Omega_\tau} G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,d\mathbf{y}, \qquad\mathbf{x}\in\Omega_\tau.
  • MτM_\tau evaluate the outgoing field on the boundary:

[Mτq](x)=∫ΩτGκ(x,y)q(y) dy,x∈Γτ.[M_\tau q](\mathbf{x}) = \int_{\Omega_\tau} G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,d\mathbf{y}, \qquad\mathbf{x}\in\Gamma_\tau.

Define the local source operator

Qτ=Lτ−1BτSτ.(9)Q^\tau= L_\tau^{-1}B_\tau S_\tau. \tag*{(9)}

Then q∣Ωτ=Qτϕτq|_{\Omega_\tau}=Q^\tau\phi_\tau, and the leaf scattering operator is

Fτ=MτQτ=MτLτ−1BτSτ.(10)F^\tau= M_\tau Q^\tau= M_\tau L_\tau^{-1}B_\tau S_\tau. \tag*{(10)}

Formula (10) will be used only on leaf boxes. For larger boxes, the scattering operator will instead be constructed by merging the operators of two smaller boxes.

Remark 1 (Equivalent-source formulation). The field-to-field scattering operator used throughout the main text is not the only possible boundary representation. An alternative is to continue representing the incoming field by its trace ϕτ\phi_\tau, but to represent the outgoing field by an equivalent single-layer source density supported on Γτ\Gamma_\tau. This leads to a closely related hierarchical merge in which interactions between children are evaluated directly through single-layer potentials. We use the field-to-field formulation in the main text because it proved simpler to implement and avoids the reconstruction of equivalent source densities. The alternative formulation is recorded in Appendix A.

Merging scattering operators

Suppose that a subdomain Ωτ\Omega_\tau is formed as a union Ωτ=Ωα∪Ωβ\Omega_\tau= \Omega_\alpha\cup\Omega_\beta of two smaller subdomains Ωα\Omega_\alpha and Ωβ\Omega_\beta, and that the scattering operators FαF^\alpha and FβF^\beta for the two “children” have already been constructed. We will show how to form the scattering operator FτF^\tau for the “parent” using boundary-to-boundary operations only. Once the scattering operator of a box has been built, we never need to revisit its interior during the upward pass.

To introduce the merge in the cleanest possible setting, we first consider two children that are separated in space. We then turn to the case of two adjacent boxes, which is the case required by the hierarchical solver. The second derivation involves additional bookkeeping, but the underlying algebra is the same.

Merging two separated boxes

Consider a scattering potential supported in two disjoint boxes Ωα\Omega_\alpha and Ωβ\Omega_\beta, and suppose that FαF^\alpha and FβF^\beta have been built, cf. Figure 3. Set

Merging of two scattering operators

Figure 3. Merging of two scattering operators, as discussed in § 3.1. Let Ωα\Omega_\alpha and Ωβ\Omega_\beta be two boxes, with the union Ωτ=Ωα∪Ωβ\Omega_\tau= \Omega_\alpha\cup\Omega_\beta. If the scattering operators FαF^\alpha and FβF^\beta have been constructed, then the joint scattering operator FτF^\tau can be constructed without the need to revisit the interiors of Ωα\Omega_\alpha or Ωβ\Omega_\beta; only operators supported on the boundaries are involved. The parent operator maps the incoming trace ϕτ\phi_\tau to the outgoing trace ψτ\psi_\tau.

Ωτ=Ωα∪Ωβ,Γτ=Γα∪Γβ.\Omega_\tau= \Omega_\alpha\cup\Omega_\beta,\qquad\Gamma_\tau= \Gamma_\alpha\cup\Gamma_\beta.

Since the boxes are separated, the boundary of the parent is simply the disjoint union of the two child boundaries. (For this introductory derivation, we temporarily allow the parent domain Ωτ\Omega_\tau to be disconnected; the hierarchical solver itself will use only adjacent rectangular children.)

Let ϕτ\phi_\tau denote the trace on Γτ\Gamma_\tau of an externally applied incoming field. Since Γτ=Γα∪Γβ\Gamma_\tau= \Gamma_\alpha\cup\Gamma_\beta, we regard ϕτ\phi_\tau as a two-component trace ordered by (Γα,Γβ)(\Gamma_\alpha,\Gamma_\beta). Note that ϕτ≠[ϕα,ϕβ]T\phi_\tau\ne[\phi_\alpha,\phi_\beta]^{\mathsf{T}}, because in the latter quantities we must also consider the interaction between α\alpha and β\beta. For later convenience (see § 3.2), we introduce

η=[ϕαϕβ]andγ=[ψαψβ].\eta= \begin{bmatrix} \phi_\alpha\\ \phi_\beta\end{bmatrix} \qquad\text{and}\qquad \gamma= \begin{bmatrix} \psi_\alpha\\ \psi_\beta\end{bmatrix}.

Introduce the block-diagonal child scattering operator

F=[Fα00Fβ],(11)F = \begin{bmatrix} F^\alpha& 0 \\ 0 & F^\beta\end{bmatrix}, \tag*{(11)}

so that

γ=Fη.(12)\gamma= F\eta. \tag*{(12)}

The sibling-generated incoming field is obtained by propagating each outgoing field to the other box. Let Eα,βE_{\alpha,\beta} denote the operator that takes the outgoing trace on Γβ\Gamma_\beta, reconstructs the corresponding radiating exterior Helmholtz field, and evaluates this field on Γα\Gamma_\alpha. Define Eβ,αE_{\beta,\alpha} analogously, and set

Eτ=[0Eα,βEβ,α0].(13)E_\tau= \begin{bmatrix} 0 & E_{\alpha,\beta} \\ E_{\beta,\alpha} & 0 \end{bmatrix}. \tag*{(13)}

The total incoming trace on each child is the sum of the externally applied field and the field generated by its sibling. Thus

η=ϕτ+Eτγ.(14)\eta= \phi_\tau+ E_\tau\gamma. \tag*{(14)}

Combining (12) and (14), we obtain the equilibrium equation for the local incoming fields

[ϕαϕβ]=ϕτ+[0Eα,βEβ,α0][Fα00Fβ][ϕαϕβ].\begin{bmatrix} \phi_\alpha\\ \phi_\beta \end{bmatrix} = \phi_\tau + \begin{bmatrix} 0 & E_{\alpha,\beta} \\ E_{\beta,\alpha} & 0 \end{bmatrix} \begin{bmatrix} F_\alpha& 0 \\ 0 & F_\beta \end{bmatrix} \begin{bmatrix} \phi_\alpha\\ \phi_\beta \end{bmatrix}.

or, more compactly,

η=ϕτ+EτFη.\eta= \phi_\tau+ E_\tau F\eta.

This motivates the following definition.

Definition 1 (Solution-transfer operator). The solution-transfer operator for the separated pair is

Tτ=(I−EτF)−1.(15)T^\tau= (I-E_\tau F)^{-1}. \tag*{(15)}

It maps the incoming trace on the parent to the total incoming traces experienced by the two children:

η=Tτϕτ.(16)\eta= T^\tau\phi_\tau. \tag*{(16)}

We assume that the local Dirichlet problems and the parent scattering problem are uniquely solvable, so that the inverse in the merge formula (15) exists.

It remains to form the outgoing trace ψτ\psi_\tau of the composite scatterer. On Γα\Gamma_\alpha, the total outgoing field is the sum of the field generated by α\alpha and the field generated by β\beta; the analogous statement holds on Γβ\Gamma_\beta. Consequently,

ψτ=(I+Eτ)γ.(17)\psi_\tau= (I+E_\tau)\gamma. \tag*{(17)}

Combining (12), (16), and (17), we obtain

Tτ=(I−EτF)−1,Fτ=(I+Eτ)FTτ.(18)T^\tau= (I-E_\tau F)^{-1}, \qquad F^\tau= (I+E_\tau)FT^\tau. \tag*{(18)}

Thus the parent scattering operator and the information needed to recover the fields on its children are both constructed using boundary-to-boundary operators only.

Remark 2 (Multiple scattering). The solution-transfer operator (15) has a natural physical interpretation in terms of repeated scattering between the children. Observe that

Tτ=(I−EτF)−1=I+EτF+(EτF)2+(EτF)3+⋯ ,(19)T^\tau= (I-E_\tau F)^{-1} = I+E_\tau F+(E_\tau F)^2+(E_\tau F)^3+\cdots, \tag*{(19)}

whenever the series converges. The term EτFE_\tau F represents one scattering event followed by propagation to the sibling, (EτF)2(E_\tau F)^2 represents two successive interactions, and so forth. Thus TτT^\tau incorporates all orders of multiple scattering between the children.

Merging two adjacent boxes

Consider next a case where the two boxes α\alpha and β\beta directly touch, as illustrated in Figure 4. This is the situation of immediate relevance to our hierarchical solution process, since it consists of pairwise merging of domains to build scattering operators for larger and larger subdomains. Let

Figure 4. Two adjacent boxes to be merged. The labels 1, 2, 3, 4 refer to boundary pieces. The labels 3 and 4 denote two copies of the same artificial interface, so that the two children may carry distinct trace variables and, after discretization, distinct grids. The support of bb may cross this interface.

∂Ωα=Γ1∪Γ3,∂Ωβ=Γ2∪Γ4,\partial\Omega_\alpha= \Gamma_1 \cup\Gamma_3,\qquad\partial\Omega_\beta= \Gamma_2 \cup\Gamma_4,

where Γ3=Γ4\Gamma_3 = \Gamma_4 is the common interface. The parent box Ωτ=Ωα∪Ωβ\Omega_\tau= \Omega_\alpha\cup\Omega_\beta has boundary

Γτ=Γ1∪Γ2.\Gamma_\tau= \Gamma_1 \cup\Gamma_2.

We use two labels for the common interface because its traces belong to different child boxes, and because the two copies may later be discretized differently.

The adjacent case differs from the separated case in three ways. First, the externally applied incoming trace on the parent boundary does not include its values on the common interface, so these values must be reconstructed. Second, the sibling-evaluation operator contains identity blocks on the common interface; this makes computations cheaper, but requires additional notational machinery. Third, the child outgoing traces include the common interface, which must be eliminated when the outgoing trace of the parent is formed.

Continuing the externally applied incoming field to the child boundaries

Let ϕτ\phi_\tau denote the incoming trace on the parent boundary Γτ\Gamma_\tau. The corresponding field satisfies the homogeneous Helmholtz equation throughout Ωτ\Omega_\tau, so its trace on the common interface can be reconstructed by solving the interior Dirichlet problem on Ωτ\Omega_\tau. We define the incoming continuation operator UτU_\tau to map ϕτ\phi_\tau to the trace of this same field on the complete boundaries of the two children. In the boundary ordering (1,2,3,4)(1,2,3,4), this operator has the form

Uτ=[I00IU31U32U41U42],(20)U_\tau= \begin{bmatrix} I & 0 \\ 0 & I \\ U_{31} & U_{32} \\ U_{41} & U_{42} \end{bmatrix}, \tag*{(20)}

so that UτϕτU_\tau\phi_\tau gives the trace of the externally applied incoming field on the complete boundaries of the two children. Since Γ3=Γ4\Gamma_3 = \Gamma_4, the third and fourth components of UτϕτU_\tau\phi_\tau agree at the continuum level; equivalently, U31=U41U_{31} = U_{41} and U32=U42U_{32} = U_{42}.

Resolving the interaction between the children

We now split the scattering operators of the children according to their exterior and interface boundary pieces:

Fα=[F11αF13αF31αF33α],Fβ=[F22βF24βF42βF44β].(21)F^\alpha= \begin{bmatrix} F^\alpha_{11} & F^\alpha_{13} \\ F^\alpha_{31} & F^\alpha_{33} \end{bmatrix}, \qquad F^\beta= \begin{bmatrix} F^\beta_{22} & F^\beta_{24} \\ F^\beta_{42} & F^\beta_{44} \end{bmatrix}. \tag*{(21)}

In the boundary ordering (1,2,3,4)(1, 2, 3, 4), define

F=[F11α0F13α00F22β0F24βF31α0F33α00F42β0F44β].(22)F = \begin{bmatrix} F_{11}^{\alpha} & 0 & F_{13}^{\alpha} & 0 \\ 0 & F_{22}^{\beta} & 0 & F_{24}^{\beta} \\ F_{31}^{\alpha} & 0 & F_{33}^{\alpha} & 0 \\ 0 & F_{42}^{\beta} & 0 & F_{44}^{\beta} \end{bmatrix}. \tag*{(22)}

Thus FF simply applies the scattering operator of each child to the appropriate pair of boundary traces. With the ordering introduced above, the total incoming and outgoing traces η,γ\eta,\gamma on the two children from § 3.1 become

η=[η1η2η3η4]andγ=[γ1γ2γ3γ4],\eta= \begin{bmatrix} \eta_1 \\ \eta_2 \\ \eta_3 \\ \eta_4 \end{bmatrix} \quad\text{and}\quad \gamma= \begin{bmatrix} \gamma_1 \\ \gamma_2 \\ \gamma_3 \\ \gamma_4 \end{bmatrix},

with

ϕα=[η1η3],ϕβ=[η2η4],ψα=[γ1γ3],ψβ=[γ2γ4].\phi_{\alpha} = \begin{bmatrix} \eta_1 \\ \eta_3 \end{bmatrix}, \qquad \phi_{\beta} = \begin{bmatrix} \eta_2 \\ \eta_4 \end{bmatrix}, \qquad \psi_{\alpha} = \begin{bmatrix} \gamma_1 \\ \gamma_3 \end{bmatrix}, \qquad \psi_{\beta} = \begin{bmatrix} \gamma_2 \\ \gamma_4 \end{bmatrix}.

The child scattering relations are simply, cf. (12),

γ=Fη.(23)\gamma= F\eta. \tag*{(23)}

Define EτE_{\tau} to be the operator that maps the child outgoing traces to the incoming traces generated on the sibling. On the common interface, no exterior solve is required: the outgoing trace from one child is directly the incoming trace generated on the other child. In the ordering (1,2,3,4)(1, 2, 3, 4),

Eτ=[0E120E14E210E230000I00I0].(24)E_{\tau} = \begin{bmatrix} 0 & E_{12} & 0 & E_{14} \\ E_{21} & 0 & E_{23} & 0 \\ 0 & 0 & 0 & I \\ 0 & 0 & I & 0 \end{bmatrix}. \tag*{(24)}

The total incoming trace on each child is the sum of the parent incoming field, continued to the child boundary, and the field generated by its sibling. Thus, cf. (14),

η=Uτϕτ+Eτγ.(25)\eta= U_{\tau}\phi_{\tau} + E_{\tau}\gamma. \tag*{(25)}

Combining (23) and (25), we find

η=Uτϕτ+EτFη,\eta= U_{\tau}\phi_{\tau} + E_{\tau}F\eta,

or

(I−EτF)η=Uτϕτ.(I - E_{\tau}F)\eta= U_{\tau}\phi_{\tau}.

We define the solution-transfer operator for the parent box by

Tτ=(I−EτF)−1Uτ.(26)T^{\tau} = (I - E_{\tau}F)^{-1}U_{\tau}. \tag*{(26)}

Then

η=Tτϕτ.(27)\eta= T^{\tau}\phi_{\tau}. \tag*{(27)}

The operator TτT^{\tau} will be used twice: it enters the construction of the parent scattering operator during the upward pass, and it transfers the incoming trace on a parent to the total incoming traces on its children during the downward pass.

Forming the parent outgoing field

The outgoing traces in γ\gamma are tabulated on the complete child boundaries, including the common interface. The outgoing trace of the parent is required only on Γτ=Γ1∪Γ2\Gamma_\tau= \Gamma_1 \cup\Gamma_2 and must include the fields generated by both children. We therefore introduce the outgoing assembly operator RτR_\tau by

ψτ=Rτγ.(28)\psi_\tau= R_\tau\gamma. \tag*{(28)}

In the ordering (1,2,3,4)(1, 2, 3, 4),

Rτ=[IE120E14E21IE230].(29)R_\tau= \begin{bmatrix} I & E_{12} & 0 & E_{14} \\ E_{21} & I & E_{23} & 0 \end{bmatrix}. \tag*{(29)}

Combining (23), (27), and (28), we obtain the parent scattering operator

Fτ=RτFTτ,Tτ=(I−EτF)−1Uτ.(30)F^\tau= R_\tau F T^\tau, \qquad T^\tau= (I - E_\tau F)^{-1} U_\tau. \tag*{(30)}

These are the two fundamental merge formulas.

Summary of the merge

The separated and adjacent cases are governed by the same three operations:

  1. continue the externally applied incoming field on the parent to the complete child boundaries;

  2. resolve all multiple scattering between the children;

  3. assemble the child outgoing fields into the outgoing field of the parent.

The first and third operations are represented by UτU_\tau and RτR_\tau, respectively, while the first two combine to form the solution-transfer operator TτT^\tau. If FF denotes the block operator formed from the two child scattering operators, then the generic merge is

Tτ=(I−EτF)−1Uτ,Fτ=RτFTτ.(31)T^\tau= (I - E_\tau F)^{-1} U_\tau, \qquad F^\tau= R_\tau F T^\tau. \tag*{(31)}

For separated scatterers, EτE_\tau is the operator defined in (13), Uτ=IU_\tau= I, and Rτ=I+EτR_\tau= I + E_\tau. For adjacent boxes, UτU_\tau reconstructs the externally applied incoming field on the internal interface, EτE_\tau contains identity maps across that interface, and RτR_\tau eliminates the interface while accumulating both child contributions on the parent boundary. No approximation has entered the construction in this section.

Remark 3 (Universal operators). The operators UτU_\tau, EτE_\tau, and RτR_\tau are independent of the scattering potential bb. They depend only on the box geometry and the free-space Helmholtz operator. Likewise, the leaf operators SτS_\tau and MτM_\tau are universal. All dependence on bb enters through BτB_\tau and LτL_\tau in the local Lippmann–Schwinger solve, and hence through QτQ^\tau, FτF^\tau, and TτT^\tau. Consequently, the universal operators can be precomputed and reused for different scattering potentials. On the uniform, translation-invariant trees considered here, only one copy is needed for each box size and merge orientation.

Remark 4 (Equivalent formulation and rank structure). The identity

F(I−EτF)−1=(I−FEτ)−1FF(I - E_\tau F)^{-1} = (I - F E_\tau)^{-1} F

shows that the parent scattering operator can equivalently be written as

Fτ=Rτ(I−FEτ)−1FUτ.(32)F^\tau= R_\tau(I - F E_\tau)^{-1} F U_\tau. \tag*{(32)}

This form is useful when considering possible accelerations of the merge. From (22) and (24), we obtain

FEτ=[0F11αE120F11αE14+F13αF22βE210F22βE23+F24β00F31αE120F31αE14+F33αF42βE210F42βE23+F44β0].(33)F E_\tau= \begin{bmatrix} 0 & F^{\alpha}_{11} E_{12} & 0 & F^{\alpha}_{11} E_{14} + F^{\alpha}_{13} \\ F^{\beta}_{22} E_{21} & 0 & F^{\beta}_{22} E_{23} + F^{\beta}_{24} & 0 \\ 0 & F^{\alpha}_{31} E_{12} & 0 & F^{\alpha}_{31} E_{14} + F^{\alpha}_{33} \\ F^{\beta}_{42} E_{21} & 0 & F^{\beta}_{42} E_{23} + F^{\beta}_{44} & 0 \end{bmatrix}. \tag*{(33)}

For boxes that contain a moderate number of wavelengths, numerical experiments indicate that all nonzero blocks in (33) except the (3,4)(3,4) and (4,3)(4,3) blocks have low numerical rank. The two exceptional blocks describe interactions across the common interface. They are not globally low rank, but admit hierarchically semiseparable (HSS) representations. We do not pursue this structure in the present work. Equation (33) nevertheless points to a particularly simple avenue for accelerating the method in future work. As the number of wavelengths in a box grows, the numerical ranks naturally grow as well.

The hierarchical continuum algorithm

We are now ready to describe the complete continuum algorithm for solving the Lippmann–Schwinger equation (3). The method is hierarchical. It consists of partitioning the computational domain into small leaf boxes, constructing a local scattering operator on every leaf, and then repeatedly merging pairs of child operators in an upward pass through a binary tree. The solution-transfer operators constructed during the upward pass are subsequently used to recover the incoming traces on all leaves in a downward pass.

The hierarchical partition

The computational domain Ω\Omega will always be a square or rectangle. Observe that the domain is in this context an artificial boundary box anyway. We first partition Ω\Omega into a collection of square, or possibly rectangular, leaf boxes. These should be small enough that the Lippmann–Schwinger equation restricted to a leaf can easily be solved to very high accuracy. We then construct a binary tree by hierarchically merging the boxes, making sure that all boxes on the same level are roughly of the same size; see Figure 5. The boxes are ordered so that if τ\tau is the parent of σ\sigma, then τ<σ\tau< \sigma. The root of the tree, which represents the full domain Ω\Omega, has index τ=1\tau= 1.

Enumeration of boxes in a binary tree

Figure 5. The square domain Ω\Omega is split into 4×44 \times4 leaf boxes. These are then gathered into a binary tree of successively larger boxes as described in § 4. One possible enumeration of the boxes in the tree is shown, but note that the only restriction is that if box τ\tau is the parent of box σ\sigma, then τ<σ\tau< \sigma.

Upward pass

Let NboxesN_{\mathrm{boxes}} denote the total number of boxes in the tree. The upward pass constructs the scattering operator FτF^\tau for every box and the solution-transfer operator TτT^\tau for every nonleaf box. At a leaf, we also retain the local source operator QτQ^\tau from (9), since it will be needed to recover the volume density after the incoming trace on the leaf has been found.

The root operator F1F^1 maps the incoming trace on ∂Ω\partial\Omega to the outgoing trace generated by all sources in Ω\Omega. In particular, it determines the complete exterior scattering solution without ever revisiting the interiors of the boxes.

Downward pass and recovery of the solution

Let the incoming trace on the root be

ϕ1=uin∣∂Ω.(34)\phi_1 = u_{\mathrm{in}}|_{\partial\Omega}. \tag*{(34)}

Suppose that the incoming trace ϕτ\phi_\tau has been determined for a nonleaf box τ\tau with children α\alpha and β\beta. By the definition of the solution-transfer operator,

η=Tτϕτ.(35)\eta= T^\tau\phi_\tau. \tag*{(35)}
Upwards and downward pass algorithms

Figure 6. Upwards (left) and downward (right) pass algorithms for the construction of the global scattering operator and the computation of the interior traces.

For the ordering (1,2,3,4)(1, 2, 3, 4) used in § 3.2, the incoming traces on the two children are then

ϕα=[η1η3],ϕβ=[η2η4].\phi_{\alpha} = \begin{bmatrix} \eta_{1} \\ \eta_{3} \end{bmatrix}, \qquad\phi_{\beta} = \begin{bmatrix} \eta_{2} \\ \eta_{4} \end{bmatrix}.

Applying this operation recursively from the root to the leaves determines the incoming trace on every leaf box.

Once ϕτ\phi_{\tau} is known on a leaf, its volume density is recovered independently by

q∣Ωτ=Qτϕτ(36)q|_{\Omega_{\tau}} = Q^{\tau}\phi_{\tau} \tag*{(36)}

and the incoming field for box τ\tau can be computed by

v∣Ωτ=Sτϕτ.(37)v|_{\Omega_{\tau}} = S_{\tau}\phi_{\tau}. \tag*{(37)}

The total field utot=u+uinu^{\mathrm{tot}} = u + u_{\mathrm{in}} inside the leaf box τ\tau is recovered by superposing the incoming field and the field induced by the volume density,

utot∣Ωτ=∫ΩτGκ(x,y)q(y) dy+v∣Ωτ.(38)u^{\mathrm{tot}}|_{\Omega_{\tau}} = \int_{\Omega_{\tau}} G_{\kappa}(\mathbf{x},\mathbf{y})q(\mathbf{y})\,\mathrm{d}y + v|_{\Omega_{\tau}}. \tag*{(38)}

Finally, the local scattered field is given by

u∣Ωτ=utot∣Ωτ−uin∣Ωτ.(39)u|_{\Omega_{\tau}} = u^{\mathrm{tot}}|_{\Omega_{\tau}} - u_{\mathrm{in}}|_{\Omega_{\tau}}. \tag*{(39)}

In the exterior of Ω\Omega, the scattered field can be reconstructed from the root outgoing trace

ψ1=F1ϕ1\psi_{1} = F^{1}\phi_{1}

by solving the radiating exterior Dirichlet problem.

The entire construction in § 2–§ 4 is exact at the continuum level. Approximation enters only when the operators appearing above are discretized, which is the subject of the next section.

Storage efficiency

There are several ways to reduce storage requirements. First, the scattering operators FτF^{\tau} are needed only during the upward pass. Once a parent operator FτF^{\tau} has been constructed, the scattering operators of its children may be discarded, since they are not used in the downward pass. Second, for recovery of the full interior field, the solution-transfer operators TτT^{\tau} must be retained, while the leaf source operators QτQ^{\tau} may either be stored or recomputed on demand during the downward pass. Recomputing the QτQ^{\tau}’s reduces memory usage at the expense of additional local solves. Finally, if only the root scattering operator F1F^{1} is required, neither the TτT^{\tau}’s nor the QτQ^{\tau}’s need be retained; in that case all intermediate operators may be discarded as soon as they are no longer needed.

Figure 8. Decomposition of the discretized scattering operator Fτ\mathbf{F}_{\tau} into its constituent operators (see § 5.2).

Discretization and implementation details

This section describes how we turn the continuum algorithm of § 4 into an actual numerical method.

Discretization

All boundary traces such as {ϕτ,ψτ,η,γ}\{\phi_{\tau},\psi_{\tau},\eta,\gamma\} are represented via collocation. For a leaf box τ\tau, we place pp Gauss–Legendre nodes on each side. Typically high pp is used, say p=10p=10 or p=20p=20. For larger boxes, we use the composite Gauss–Legendre grids obtained by retaining the boundary nodes of their children.

To facilitate the interior spectral solve, we also introduce a Chebyshev discretization of Ωτ\Omega_{\tau}. The tensor-product Chebyshev grid provides the interior discretization on which the Lippmann–Schwinger equation is solved. Local discretizations are shown in Figure 7.

Figure 7. Local discretization on a leaf box.

Leaf computations

As introduced in § 2.3, the task is to find the scattering operator that maps the incoming field prescribed on the boundary of a leaf box τ\tau to the corresponding outgoing scattered field on the same boundary. The leaf computations are executed on tensor-product Chebyshev grids.

Recall that, in the continuous case, FτF_{\tau} maps the incoming field ϕτ\phi_{\tau} to the outgoing field ψτ\psi_{\tau}, where ψτ\psi_{\tau} is the boundary trace of ∫ΩτG(x,y)qτ(y) dy\int_{\Omega_{\tau}}G(\mathbf{x},\mathbf{y})q_{\tau}(\mathbf{y})\,d\mathbf{y}, and qτq_{\tau} solves the local Lippmann–Schwinger equation with incoming field ϕτ\phi_{\tau}. In discretized form, the computation of Fτ\mathbf{F}_{\tau} then involves the following steps:

  • Interpolate the incoming trace from the Gauss–Legendre nodes to Chebyshev boundary nodes, averaging the two side interpolants at each corner.

  • Use a local spectral collocation solve for the homogeneous Helmholtz equation to reconstruct the incoming field at all tensor-product Chebyshev nodes.

  • Solve the local Lippmann–Schwinger equation using a high-order corrected quadrature rule to obtain the (discretized) volume density qτq_{\tau}.

  • Interpolate the trace of the volume potential generated by qτq_{\tau} to the Gauss–Legendre boundary nodes to obtain the outgoing trace.

Given an incoming field ϕGL\phi_{\mathrm{GL}} on the Gauss–Legendre boundary nodes, the operator S\mathbf{S} reconstructs the corresponding field ϕvol\phi_{\mathrm{vol}} on the tensor-product Chebyshev grid. It consists of interpolation from the Gauss–Legendre boundary nodes to the Chebyshev boundary nodes, followed by a Chebyshev spectral collocation solve of the homogeneous Helmholtz equation. Thus,

ϕvol=SϕGL.(40)\boldsymbol{\phi}_{\mathrm{vol}}=\mathbf{S}\boldsymbol{\phi}_{\mathrm{GL}}. \tag*{(40)}

The induced volume density is then computed from the discretized Lippmann–Schwinger equation,

Lqτ=Bϕvol,(41)\mathbf{L}\boldsymbol{q}_{\tau}=\mathbf{B}\boldsymbol{\phi}_{\mathrm{vol}}, \tag*{(41)}

where L=I−BG\mathbf{L}=\mathbf{I}-\mathbf{B}\mathbf{G} is the discretized Lippmann–Schwinger operator, B\mathbf{B} contains the scattering potential scaled by −κ2-\kappa^{2} and G\mathbf{G} represents the volume Green’s operator q↦∫ΩτGκ(⋅,y)q(y) dyq\mapsto\int_{\Omega_{\tau}}G_{\kappa}(\cdot,\mathbf{y})q(\mathbf{y})\,d\mathbf{y} discretized using a high-order corrected quadrature rule. Hence,

qτ=L−1BSϕGL.(42)\boldsymbol{q}_{\tau}=\mathbf{L}^{-1}\mathbf{B}\mathbf{S}\boldsymbol{\phi}_{\mathrm{GL}}. \tag*{(42)}

Finally, the scattered field generated by qq is evaluated on the Chebyshev boundary nodes and interpolated to the Gauss–Legendre boundary nodes. Denoting the resulting operator by M\mathbf{M}, we have

ψGL=Mqτ.(43)\boldsymbol{\psi}_{\mathrm{GL}}=\mathbf{M}\boldsymbol{q}_{\tau}. \tag*{(43)}

Combining the three stages gives

ψGL=ML−1BSϕGL.(44)\boldsymbol{\psi}_{\mathrm{GL}}=\mathbf{M}\mathbf{L}^{-1}\mathbf{B}\mathbf{S}\boldsymbol{\phi}_{\mathrm{GL}}. \tag*{(44)}

Therefore, the scattering matrix for leaf τ\tau is

Fτ=ML−1BS.(45)\mathbf{F}^{\tau}=\mathbf{M}\mathbf{L}^{-1}\mathbf{B}\mathbf{S}. \tag*{(45)}

The leaf continuation operators S\mathbf{S}, scattering trace operator M\mathbf{M} and the high-order quadrature matrices G\mathbf{G} are universal when all leaf boxes have the same size. They therefore need to be constructed only once.

Discretization of the merge stage

As already noted in Remark 3, the operators Eτ\mathbf{E}_{\tau}, Uτ\mathbf{U}_{\tau} and Rτ\mathbf{R}_{\tau} from (31) are universal at each level where they exist. At level ℓ=L\ell=L, there is no continuation operator (leaf nodes have no children), so we can index all discretized continuation operators by U(ℓ)\mathbf{U}^{(\ell)}, ℓ=0,…,L−1\ell=0,\ldots,L-1. Similarly (the root node has no siblings) we can index all sibling-evaluation operators by E(ℓ)\mathbf{E}^{(\ell)}, ℓ=1,…,L\ell=1,\ldots,L. For notational convenience we will drop the index ℓ\ell for the blocks and operators that constitute E(ℓ)\mathbf{E}^{(\ell)}, R(ℓ)\mathbf{R}^{(\ell)} and U(ℓ)\mathbf{U}^{(\ell)}.

As can be seen from (24) and (29), E(ℓ)\mathbf{E}^{(\ell)} and R(ℓ)\mathbf{R}^{(\ell)} can be written as

E(ℓ)=[0E120E14E210E230000I00I0],R(ℓ)=[IE120E14E21IE230].(46)\mathbf{E}^{(\ell)}= \begin{bmatrix} \mathbf{0} & \mathbf{E}_{12} & \mathbf{0} & \mathbf{E}_{14}\\ \mathbf{E}_{21} & \mathbf{0} & \mathbf{E}_{23} & \mathbf{0}\\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{I}\\ \mathbf{0} & \mathbf{0} & \mathbf{I} & \mathbf{0} \end{bmatrix}, \qquad \mathbf{R}^{(\ell)}= \begin{bmatrix} \mathbf{I} & \mathbf{E}_{12} & \mathbf{0} & \mathbf{E}_{14}\\ \mathbf{E}_{21} & \mathbf{I} & \mathbf{E}_{23} & \mathbf{0} \end{bmatrix}. \tag*{(46)}

Figure 9 shows the set-up for U(ℓ−1)\mathbf{U}^{(\ell-1)} and E21,E23\mathbf{E}_{21},\mathbf{E}_{23}. The construction for E12,E14\mathbf{E}_{12},\mathbf{E}_{14} is similar. Computationally, the structure of [E21,E23][\mathbf{E}_{21},\mathbf{E}_{23}] is

Set-up for the discretization of $\mathbf{U}^{(\ell-1)}$ and $\mathbf{E}^{(\ell)}$.

Figure 9. Set-up for the discretization of U(ℓ−1)\mathbf{U}^{(\ell-1)} and E(ℓ)\mathbf{E}^{(\ell)}.

[E21,E23]=BIEeval(ext)∘BIEsolve(ext)∘Interp.[\mathbf{E}_{21},\mathbf{E}_{23}] = \mathbf{BIE}^{(\mathrm{ext})}_{\mathrm{eval}} \circ \mathbf{BIE}^{(\mathrm{ext})}_{\mathrm{solve}} \circ \mathbf{Interp}.

Here Interp\mathbf{Interp} maps the boundary data, collocated at piecewise Gauss-Legendre nodes, to interpolated boundary data at a point distribution on the boundary that is suited for a BIE solver. The exterior BIE solver BIEsolve(ext)\mathbf{BIE}^{(\mathrm{ext})}_{\mathrm{solve}} solves for a (discrete) surface density, whose precise form depends on the chosen formulation. Finally, BIEeval(ext)\mathbf{BIE}^{(\mathrm{ext})}_{\mathrm{eval}} maps the resulting surface density to the values of the Helmholtz solution at the specified exterior target DOFs. The matrix U(ℓ−1)\mathbf{U}^{(\ell-1)} has the same structure, but interior:

U(ℓ−1)=BIEeval(int)∘BIEsolve(int)∘Interp.\mathbf{U}^{(\ell-1)} = \mathbf{BIE}^{(\mathrm{int})}_{\mathrm{eval}} \circ \mathbf{BIE}^{(\mathrm{int})}_{\mathrm{solve}} \circ \mathbf{Interp}.

In our implementation we use Brakhage–Werner-type indirect BIE formulations for both the exterior and interior problem. Concretely:

BIEsolve(int)=(DL+iζSL+12I)−1,BIEsolve(ext)=(DL+iζSL−12I)−1\mathbf{BIE}^{(\mathrm{int})}_{\mathrm{solve}} = \left( \mathbf{D}\mathbf{L} +i\zeta\mathbf{S}\mathbf{L} +\frac{1}{2}\mathbf{I} \right)^{-1}, \qquad \mathbf{BIE}^{(\mathrm{ext})}_{\mathrm{solve}} = \left( \mathbf{D}\mathbf{L} +i\zeta\mathbf{S}\mathbf{L} -\frac{1}{2}\mathbf{I} \right)^{-1}

with DL and SL discretizations of the boundary double-layer and boundary single-layer operators (here SL is not to be confused with the product of S and L from § 5.2) and ξ∈R\xi\in\mathbb{R} is a scalar usually chosen to be ±κ\pm\kappa. We construct and solve both using the chunkIE package (see [4]).

For a fixed level ℓ\ell, U(ℓ)\mathbf{U}^{(\ell)} and E(ℓ)\mathbf{E}^{(\ell)} are defined on the same boundary. As such, the matrices DL and SL can be re-used for the construction of E(ℓ)\mathbf{E}^{(\ell)} and U(ℓ)\mathbf{U}^{(\ell)}.

Complexity

The complexity of our proposed solver is dominated by the following three terms:

  1. cleafc_{\mathrm{leaf}}: the construction, at the leaf level, of Qτ\mathbf{Q}_{\tau} and Fτ\mathbf{F}_{\tau}.

  2. cprec_{\mathrm{pre}}: the off-line computation, at each level, of E(ℓ)\mathbf{E}^{(\ell)}, U(ℓ)\mathbf{U}^{(\ell)} and R(ℓ)\mathbf{R}^{(\ell)}.

  3. cinvc_{\mathrm{inv}}: the inversion, at each level, of (I−E(ℓ)F)(\mathbf{I}-\mathbf{E}^{(\ell)}\mathbf{F}).

We set N=p2⋅2LN=p^2 \cdot2^L to be the total number of unreduced degrees of freedom. For simplicity we assume that LL is even.

The leaf scattering computation cleafc_{\mathrm{leaf}} is dominated by the inversion of Lτ\mathbf{L}_{\tau}, which is of order O(p6)\mathcal{O}(p^6). The total cost cleafc_{\mathrm{leaf}} is therefore

cleaf=O(p62L)=O(p4N).c_{\mathrm{leaf}}=\mathcal{O}(p^6 2^L)=\mathcal{O}(p^4N).

Usually, the leaf level matrices are quite small. Even at p=30p=30, they are only of size 900×900900 \times900, making them perfectly suited for highly efficient BLAS level 3 operations.

The cost cinvc_{\mathrm{inv}}, by a geometric series argument, is bounded by a constant times the cost of the inversion of (I−E(0)F)(\mathbf{I}-\mathbf{E}^{(0)}\mathbf{F}) at the root, where the size of the system is precisely 2L/2p×2L/2p=N×N2^{L/2}p \times2^{L/2}p=\sqrt{N}\times\sqrt{N}. Then, trivially,

cinv=O(N3/2).c_{\mathrm{inv}}=\mathcal{O}(N^{3/2}).

The cost cprec_{\mathrm{pre}} depends heavily on the chosen BIE solvers. We present the argument for the continuation matrices U(ℓ)\mathbf{U}^{(\ell)}, ℓ=1,…,L\ell=1,\ldots,L here, but the same argument applies to the sibling evaluation operators.

Assume that the system matrices BIEsolve(int)\mathbf{BIE}_{\mathrm{solve}}^{(\mathrm{int})} at level ℓ\ell are square and of size nBIE(ℓ)×nBIE(ℓ)n_{\mathrm{BIE}}^{(\ell)}\times n_{\mathrm{BIE}}^{(\ell)}. With cℓc_{\ell} the number of boundary segments of a box at level ℓ\ell, we ensure nBIE(ℓ)=O(cℓp)=O(2(L−ℓ)/2p)n_{\mathrm{BIE}}^{(\ell)}=\mathcal{O}(c_{\ell}p)=\mathcal{O}(2^{(L-\ell)/2}p). Naive construction and inversion of the BIE system results in a cost of O((nBIE(ℓ))2+(nBIE(ℓ))3)\mathcal{O}((n_{\mathrm{BIE}}^{(\ell)})^2+(n_{\mathrm{BIE}}^{(\ell)})^3). The cost of applying interpolation and evaluation by Interp, BIEeval(int)\mathbf{BIE}_{\mathrm{eval}}^{(\mathrm{int})} scales as follows: at level ℓ\ell these operators are block diagonal matrices, consisting of O(2L−ℓ)\mathcal{O}(2^{L-\ell}) blocks. Each of the blocks in the interpolation (resp. evaluation) can be of variable row size (resp. column size), but always has column size (resp. row size) pp. This means the cost multiplying BIEsolve(int)\mathrm{BIE}_{\mathrm{solve}}^{(\mathrm{int})} left and right by these block diagonal matrices is bounded by O(p(nBIE(ℓ))2)\mathcal{O}(p(n_{\mathrm{BIE}}^{(\ell)})^2).

Summing over levels, again using a geometric series argument, finally gives us

cpre=O(∑ℓ(p(nBIE(ℓ))2+(nBIE(ℓ))3))=O(N3/2).c_{\mathrm{pre}}=\mathcal{O}\left(\sum_{\ell}\left(p(n_{\mathrm{BIE}}^{(\ell)})^2+(n_{\mathrm{BIE}}^{(\ell)})^3\right)\right)=\mathcal{O}(N^{3/2}).

The final estimate on the right-hand side obfuscates the dependence of the off-line phase on the chosen BIE solver, and for this reason we present both complexity estimates. While we have presented the asymptotic cost for naive BIE construction and inversion, at large scale both can be accelerated using fast algorithms like the Fast Multipole Method (FMM, see, e.g., [24, 33, 38]), hierarchical matrix techniques (see [5, 23, 30]) and recursive compression (see [25]).

Numerical examples

We present six numerical experiments with various wavenumbers κ\kappa and scattering potentials b(x)b(\mathbf{x}). The computational domain is the unit square [0,1]2[0,1]^2. The numerical computations in this section were carried out using MATLAB. All timings are reported on a workstation with an Intel(R) Xeon(R) Gold 6248R processor (48 cores with 2 threads per core at 3.00 GHz base frequency) and 1.5 TB of RAM. Results are presented in Table 1 and Table 2.

levelsNumber of leavesNumber of pointsprecomp.buildeval.solve
nleveln_{\mathrm{level}}nleavesn_{\mathrm{leaves}}NtotN_{\mathrm{tot}}tprecompt_{\mathrm{precomp}}tbuildt_{\mathrm{build}}tevalt_{\mathrm{eval}}tsolvet_{\mathrm{solve}}
3416001.35×1011.35 \times10^{1}5.80×10−25.80 \times10^{-2}4.16×10−24.16 \times10^{-2}5.11×10−35.11 \times10^{-3}
51664001.75×1011.75 \times10^{1}2.49×10−12.49 \times10^{-1}4.36×10−24.36 \times10^{-2}1.09×10−21.09 \times10^{-2}
76425 6002.14×1012.14 \times10^{1}9.18×10−19.18 \times10^{-1}4.58×10−24.58 \times10^{-2}4.26×10−24.26 \times10^{-2}
9256102 4002.59×1012.59 \times10^{1}4.70×1004.70 \times10^{0}3.88×10−23.88 \times10^{-2}1.82×10−11.82 \times10^{-1}
111024409 6003.04×1013.04 \times10^{1}1.96×1011.96 \times10^{1}4.14×10−24.14 \times10^{-2}6.80×10−16.80 \times10^{-1}
1340961 638 4003.78×1013.78 \times10^{1}8.36×1018.36 \times10^{1}5.10×10−25.10 \times10^{-2}2.48×1002.48 \times10^{0}
1516 3846 553 6004.93×1014.93 \times10^{1}3.74×1023.74 \times10^{2}7.05×10−27.05 \times10^{-2}2.18×1012.18 \times10^{1}

Table 1. Computational cost for different numbers of levels, at κ=77.1\kappa= 77.1 and p=20p = 20.

Scattering potentiallevels nleveln_{\mathrm{level}}leaves nleavesn_{\mathrm{leaves}}points NtotN_{\mathrm{tot}}ext. EextE_{\mathrm{ext}}int. EintE_{\mathrm{int}}grid EgridE_{\mathrm{grid}}
Gaussian bump3416003.11×10−73.11 \times10^{-7}3.54×10−53.54 \times10^{-5}1.89×10−51.89 \times10^{-5}
51664001.22×10−91.22 \times10^{-9}2.47×10−72.47 \times10^{-7}5.55×10−75.55 \times10^{-7}
76425 6002.00×10−102.00 \times10^{-10}2.33×10−82.33 \times10^{-8}1.58×10−71.58 \times10^{-7}
9256102 4001.73×10−101.73 \times10^{-10}3.86×10−83.86 \times10^{-8}8.22×10−88.22 \times10^{-8}
111024409 6001.88×10−101.88 \times10^{-10}1.65×10−81.65 \times10^{-8}3.53×10−83.53 \times10^{-8}
Smooth mollifier3416005.69×10−55.69 \times10^{-5}2.90×10−42.90 \times10^{-4}2.83×10−42.83 \times10^{-4}
51664001.41×10−61.41 \times10^{-6}8.88×10−68.88 \times10^{-6}9.69×10−69.69 \times10^{-6}
76425 6003.60×10−103.60 \times10^{-10}8.03×10−88.03 \times10^{-8}1.06×10−71.06 \times10^{-7}
9256102 4003.94×10−103.94 \times10^{-10}2.43×10−82.43 \times10^{-8}3.36×10−83.36 \times10^{-8}
111024409 6004.26×10−104.26 \times10^{-10}7.23×10−97.23 \times10^{-9}3.47×10−83.47 \times10^{-8}
Cavity3416002.50×10−22.50 \times10^{-2}6.76×10−26.76 \times10^{-2}6.24×10−26.24 \times10^{-2}
51664003.55×10−53.55 \times10^{-5}2.90×10−42.90 \times10^{-4}1.33×10−41.33 \times10^{-4}
76425 6001.04×10−91.04 \times10^{-9}9.91×10−89.91 \times10^{-8}3.94×10−73.94 \times10^{-7}
9256102 4008.23×10−108.23 \times10^{-10}3.08×10−83.08 \times10^{-8}2.90×10−72.90 \times10^{-7}
111024409 6007.49×10−107.49 \times10^{-10}4.14×10−94.14 \times10^{-9}1.61×10−71.61 \times10^{-7}
Lens33416001.00×1011.00 \times10^{1}1.75×1011.75 \times10^{1}3.35×1013.35 \times10^{1}
51664001.01×1011.01 \times10^{1}8.59×1028.59 \times10^{2}2.54×1032.54 \times10^{3}
76425 6005.19×10−15.19 \times10^{-1}9.52×10−19.52 \times10^{-1}3.67×1003.67 \times10^{0}
9256102 4002.37×10−52.37 \times10^{-5}4.62×10−44.62 \times10^{-4}3.10×10−43.10 \times10^{-4}
111024409 6001.36×10−71.36 \times10^{-7}8.45×10−78.45 \times10^{-7}3.87×10−63.87 \times10^{-6}
1340961 638 4006.16×10−86.16 \times10^{-8}1.76×10−71.76 \times10^{-7}1.34×10−61.34 \times10^{-6}
1516 3846 553 6004.52×10−84.52 \times10^{-8}1.12×10−71.12 \times10^{-7}9.03×10−79.03 \times10^{-7}
Photonic crystal43416001.09×1001.09 \times10^{0}2.54×1002.54 \times10^{0}5.98×1005.98 \times10^{0}
51664004.09×10−14.09 \times10^{-1}8.49×10−18.49 \times10^{-1}1.43×1001.43 \times10^{0}
76425 6003.45×10−13.45 \times10^{-1}1.27×1001.27 \times10^{0}2.68×1012.68 \times10^{1}
9256102 4001.26×10−11.26 \times10^{-1}3.09×10−13.09 \times10^{-1}6.25×1006.25 \times10^{0}
111024409 6001.17×10−61.17 \times10^{-6}4.33×10−54.33 \times10^{-5}3.08×10−53.08 \times10^{-5}
1340961 638 4003.48×10−83.48 \times10^{-8}2.25×10−72.25 \times10^{-7}2.26×10−62.26 \times10^{-6}
1516 3846 553 6001.05×10−81.05 \times10^{-8}4.68×10−84.68 \times10^{-8}4.57×10−74.57 \times10^{-7}
Pyramid53416001.08×10−31.08 \times10^{-3}2.35×10−32.35 \times10^{-3}2.26×10−32.26 \times10^{-3}
51664002.38×10−42.38 \times10^{-4}6.89×10−46.89 \times10^{-4}1.00×10−31.00 \times10^{-3}
76425 6004.84×10−54.84 \times10^{-5}1.23×10−41.23 \times10^{-4}4.17×10−44.17 \times10^{-4}
9256102 4001.23×10−51.23 \times10^{-5}2.32×10−52.32 \times10^{-5}1.19×10−41.19 \times10^{-4}
111024409 6002.57×10−62.57 \times10^{-6}5.07×10−65.07 \times10^{-6}2.76×10−52.76 \times10^{-5}
1340961 638 4007.23×10−77.23 \times10^{-7}1.39×10−61.39 \times10^{-6}7.94×10−67.94 \times10^{-6}
1516 3846 553 6002.05×10−72.05 \times10^{-7}3.94×10−73.94 \times10^{-7}2.26×10−62.26 \times10^{-6}

Table 2. Results of the proposed method for six scattering potentials.

We note the following quantities:

  • nleveln_{\mathrm{level}} The number of levels of the hierarchical tree.

  • nleavesn_{\mathrm{leaves}} The number of leaves on the finest level.

  • NtotN_{\mathrm{tot}} The total number of degrees of freedom.

  • tprecompt_{\mathrm{precomp}} Time in seconds to precompute the S,M,G,E,U,R\mathbf{S},\mathbf{M},\mathbf{G},\mathbf{E},\mathbf{U},\mathbf{R} matrices.

  • tbuildt_{\mathrm{build}} Time in seconds to build scattering matrices F\mathbf{F}.

  • tevalt_{\mathrm{eval}} Time in seconds to evaluate exterior field.

  • tsolvet_{\mathrm{solve}} Time in seconds to solve for interior field.

  • EextE_{\mathrm{ext}} The relative error in the exterior field (total field) evaluated at selected points.

  • EintE_{\mathrm{int}} The relative error in the interior field (total field) evaluated at selected off-grid points.

  • EgridE_{\mathrm{grid}} The maximal relative error in the interior field (total field) among all tensor Chebyshev grid points.

All errors are in the L∞L^\infty-norm and obtained by comparing to a reference solution at nlevel=17n_{\mathrm{level}}=17 and p=20p=20. The total field refers to the sum of the scattered and incoming fields, i.e., utot=u+uinu^{\mathrm{tot}}=u+u_{\mathrm{in}}, as in § 4.3.

We consider six test problems, where the incident field is given by a plane wave uin(x)=exp⁡(iκ(x1−0.5))\mathbf{u}_{\mathrm{in}}(\mathbf{x})=\exp(\mathrm{i}\kappa(x_1-0.5)):

Gaussian bump: A Gaussian bump given by b(x)=1.5exp⁡(−160∥x−xc∥2)b(\mathbf{x})=1.5\exp(-160\lVert\mathbf{x}-\mathbf{x}_c\rVert^2) with κ=25\kappa=25, where xc\mathbf{x}_c is the center of the computational domain (Figure 10(a)). The computational domain is about 4 wavelengths across.

Gaussian bump

Figure 10. Gaussian bump

Smooth mollifier

caption: Smooth mollifier

Cavity

caption: Cavity

Lens

caption: Lens

Photonic crystal

caption: Photonic crystal

Pyramid

caption: Pyramid

caption: Scattering potentials b(x)b(\boldsymbol{x}).

Smooth mollifier: A smooth mollifier given by b(x)=exp⁡(−ϵ2ϵ2−∥x−xc∥2)b(\mathbf{x})=\exp\left(-\frac{\epsilon^2}{\epsilon^2-\lVert\mathbf{x}-\mathbf{x}_c\rVert^2}\right) for ∥x−xc∥<ϵ\lVert\mathbf{x}-\mathbf{x}_c\rVert<\epsilon with ϵ=0.4\epsilon=0.4 (Figure 10(b)). The wavenumber is set to κ=25\kappa=25, so that the computational domain is about 4 wavelengths across.

Cavity: A cavity potential is given in polar coordinates by b(r,θ)=(1−sin⁡(0.5θ)500)exp⁡(−2000(0.1−r2)2)b(r,\theta)=(1-\sin(0.5\theta)^{500})\exp(-2000(0.1-r^2)^2) (Figure 10(c)). The wavenumber is set to κ=50.27\kappa=50.27, so that the computational domain is about 8 wavelengths across.

Lens: A vertically-graded lens given by b(x)=4(x2−0.7)[1−erf⁡(25(∥x−xc∥−0.3))]b(\mathbf{x})=4(x_2-0.7)\left[1-\operatorname{erf}(25(\lVert\mathbf{x}-\mathbf{x}_c\rVert-0.3))\right] with κ=200\kappa=200 (Figure 10(d)). The computational domain is about 31.8 wavelengths across.

Photonic crystal: A 20 by 20 square grid of Gaussian bumps with a channel removed with κ=77.1\kappa=77.1 (the first complete band gap) (Figure 10(e)). The computational domain is about 12.2 wavelengths across.

Pyramid: A pyramid potential given by b(x)=max⁡(1−∣x1−0.5∣+∣x2−0.5∣0.4,0)b(\mathbf{x})=\max\left(1-\frac{|x_1-0.5|+|x_2-0.5|}{0.4},0\right) with κ=25\kappa=25 (Figure 10(f)). The computational domain is about 4 wavelengths across.

Table 1 reports the computational cost of the algorithm for increasing numbers of levels. As the hierarchy is refined from 3 to 15 levels, the precomputation time increases from 13.5 s to 49.3 s, reflecting the additional cost associated with constructing the operators required at each level of the hierarchy. In contrast, the evaluation time remains nearly constant despite the substantial increase in problem size. The build and solve times exhibit more pronounced growth, roughly linear in terms of NtotN_{\mathrm{tot}}. These results demonstrate that the computational cost of the hierarchical merge is dominated increasingly by the construction and solution stages as the number of levels increases, whereas the evaluation stage remains relatively insensitive to the overall problem size.

Table 2 summarizes the convergence behavior of the hierarchical merge for six scattering potentials. For the Gaussian bump, smooth mollifier, and cavity test cases, the exterior, interior on-grid and off-grid errors decrease rapidly with refinement, reaching errors between approximately 10−1010^{-10} and 10−810^{-8} at the finest resolution. The lens and photonic-crystal examples are more demanding on coarse grids and require substantially finer discretizations before achieving high accuracy. In particular, the lens errors decrease from O(1)O(1) at three levels to below 10−710^{-7} at fifteen levels, while the photonic-crystal errors exhibit a substantial reduction at eleven levels, and decrease gradually until the finest resolution. Additionally the BIE operators from § 5.3 are refined in this case (i.e., nBIEn_{\mathrm{BIE}} is increased, see § 5.4). The pyramid case, since its bb-function is only C0C^{0}, converges more gradually. Overall, these results demonstrate that the hierarchical merge produces convergent solutions across a range of smooth and highly structured scattering potentials, while the resolution required to attain a given accuracy depends on the complexity of the scattering potential. For the smooth examples, the errors eventually plateau under further refinement. We suspect that this behavior is primarily due to limitations in the accuracy of the boundary integral evaluations used to construct the universal operators, particularly for targets very close to the boundary.

Total field for different scattering potentials: (a) Gaussian bump, (b) Smooth mollifier, (c) Cavity, (d) Lens, (e) Photonic crystal, (f) Pyramid

Figure 11. (a) Gaussian bump; (b) Smooth mollifier; (c) Cavity; (d) Lens; (e) Photonic crystal; (f) Pyramid. Total field for different scattering potentials b(x)b(\mathbf{x}), given the incoming plane wave uin(x)=exp⁡(iκ(x1−0.5))u_{\mathrm{in}}(\mathbf{x}) = \exp(\mathrm{i}\kappa(x_1 - 0.5)).

Exterior scattering and multiple right-hand sides

The solver introduced in this manuscript is direct, so it can naturally handle multiple right hand sides. Table 3 reports the timings of simultaneously performing 500 solves, corresponding to 500 angles of incidence of plane waves.

Precomp.BuildEEMdirectfrom EEMMemory (GB)Error
Volume solver46.754.9—14.92—10.61.81×10−81.81 \times10^{-8}
Exterior scatterer45.853.91.00.292.1×10−32.1 \times10^{-3}1.251.72×10−81.72 \times10^{-8}

Table 3. Cavity scatterer (κ=201.06\kappa= 201.06, p=20p = 20, 13 levels): timings and storage for the volume solver and the exterior scatterer, for 500 incidence directions. EEM denotes the exterior evaluation matrix; the error is the ∥⋅∥∞\lVert\cdot\rVert_{\infty} difference from a fine solve.

There are also many applications in which one is only interested in the scattered field at prescribed exterior locations. Examples include lens scattering [16, 34, 31], microcavity emission [26], inverse scattering [13, 11, 36, 32, 6] and photonic crystal scattering [27, 35]. Significant effort has gone into designing specialized solvers to compute only the exterior scattered field (see, e.g., [9, 10, 21]). In the present formulation, such a specialized solver is easily obtained by only retaining the root scatterer F1\mathbf{F}^{1}. As Table 3 shows, this leads to large memory savings and significant speed-up.

Magnitude of the total field for various incoming wave angles

Figure 12. Magnitude of the total field utotu_{\mathrm{tot}} for various incoming wave angles θ\theta. Top: global field. Bottom: Field measured at an exterior receiver array (indicated in black).

Two types of exterior scattering are considered in Table 3, which differ in the way the obtained outgoing field at ∂Ω\partial\Omega is evaluated in the exterior of Ω\Omega. After the outgoing trace is computed for each incoming field by applying F1\mathbf{F}^{1}, both use the root level BIEsolve(ext)\mathbf{BIE}_{\mathrm{solve}}^{(\mathrm{ext})} on ∂Ω\partial\Omega followed by

  1. each exterior evaluation being performed separately, assuming the exterior evaluation points differ per incoming field (‘direct’), or

  2. using a precomputed exterior evaluation matrix (EEM), mapping scattered fields at ∂Ω\partial\Omega to the prescribed, shared, evaluation points (‘from EEM’).

To be precise, assume the exterior points are given in advance. As in § 5.3, BIEeval(ext)\mathbf{BIE}_{\mathrm{eval}}^{(\mathrm{ext})} evaluates an exterior Helmholtz solution to these points. Then EEM=BIEeval(ext)(BIEsolve(ext)F1)\mathrm{EEM} = \mathbf{BIE}_{\mathrm{eval}}^{(\mathrm{ext})}(\mathbf{BIE}_{\mathrm{solve}}^{(\mathrm{ext})}\mathbf{F}^{1}), with BIEsolve(ext)\mathbf{BIE}_{\mathrm{solve}}^{(\mathrm{ext})} the root-level exterior Brakhage–Werner solution operator.

In both cases, the exterior solve is orders of magnitude faster than the volume solve. Solving 500 right-hand sides, even for the volume solve, is not significantly more expensive than solving a single right-hand side (see Table 1).

Conclusions

This paper describes a high-order accurate hierarchical direct solver for the two-dimensional Lippmann–Schwinger equation arising in acoustic scattering from variable media. The essential idea is to construct a reusable field-to-field scattering operator for the inhomogeneous medium, which would avoid a new global volume solve for every incident field. Each leaf subdomain is treated by a local Lippmann–Schwinger solve, while neighboring subdomains are merged recursively through boundary-only operations. As a result, volume solves are only operated on the finest level of the hierarchy, and the remainder of the computation is performed entirely in terms of boundary traces.

The resulting method naturally separates the computation into a reusable precomputation and an application stage. Once the scattering operator for a given medium, geometry, and frequency has been constructed, it can be applied to multiple incident fields without repeating the expensive volume discretization and hierarchical construction. Numerical experiments demonstrate high-order accuracy over a range of variable-media scattering problems, including smooth potentials as well as more challenging set-ups containing cavities, high-frequency problems, strong back-scattering, and other features that can make conventional iterative approaches difficult to use efficiently. The convergence results also illustrate the effect of the regularity of the scattering potential: smooth potentials exhibit rapid convergence, whereas potentials with limited regularity converge more gradually and may eventually be limited by the polynomial order used in the discretization.

Possible future work is to study the potential rank structure of the dense matrices arising throught the hierarchy. Although these matrices are dense, many of them have global low-rank structure, and the remaining matrices often exhibit hierarchical low-rank structure, such as hierarchically semiseparable (HSS) structure. In particular, exploiting low-rank and HSS representations could reduce both the storage requirements and the computational cost of the leaf solves, merging operations, and scattering-operator applications.

Overall, the numerical results demonstrate that the proposed hierarchical formulation provides an accurate and reusable direct solver for two-dimensional Lippmann–Schwinger scattering problems. Future work will focus on systematically exploiting the low-rank and HSS structure of the operators, with the goal of developing a compressed hierarchical implementation that retains the high-order accuracy while substantially reducing memory usage, construction cost, and application time.

Acknowledgements

This work was supported by the Office of Naval Research (FP00011501), by the National Science Foundation (DMS-2608883 and DMS-2313434), and by the Simons Foundation. JB was supported in part by the Peter O’Donnell Jr. Postdoctoral Fellowship at the Oden Institute, and in part by the Swedish Research Council under grant no. 2021-06594 while in residence at Institut Mittag-Leffler in Djursholm, Sweden during the fall semester of 2025.

Equivalent-source formulation

The field-to-field formulation in the main text represents both the incoming and outgoing fields of a box by their Dirichlet traces. There is a closely related alternative in which the incoming field is still represented by its trace ϕτ\phi_\tau, but the outgoing field is represented by an equivalent source density on the boundary. We record the formulation here because its algebra is distinct, as it makes the propagation between boxes a direct layer-potential evaluation, and it may prove useful in future variants of the method. The leaf solve is essentially unchanged; what differs is the representation of the outgoing field and, consequently, the merge.

Throughout this appendix, FτF^\tau denotes the equivalent-source scattering operator, rather than the field-to-field scattering operator used in the main text.

Local equivalent-source scattering operator

Let Ωτ\Omega_\tau be a box and suppose that the incoming trace ϕτ\phi_\tau is given. As in § 2, first reconstruct the incoming field vτ=Sτϕτv_\tau= S_\tau\phi_\tau and solve the locally restricted Lippmann–Schwinger equation. Equivalently, using (9),

q∣Ωτ=Qτϕτ.\left.q\right|_{\Omega_\tau}=Q^\tau\phi_\tau.

The corresponding outgoing field is

wτ(x)=∫ΩτGκ(x,y)q(y) dy,x∈R2∖Ωτ‾.w_\tau(\mathbf{x})=\int_{\Omega_\tau}G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,d\mathbf{y},\qquad\mathbf{x}\in\mathbb{R}^2\setminus\overline{\Omega_\tau}.

Instead of representing wτw_\tau by its boundary trace, seek a density μτ\mu_\tau on Γτ\Gamma_\tau whose single-layer potential reproduces the same exterior field:

∫ΩτGκ(x,y)q(y) dy=∫ΓτGκ(x,y)μτ(y) dsy,x∈R2∖Ωτ‾.(47)\int_{\Omega_\tau}G_\kappa(\mathbf{x},\mathbf{y})q(\mathbf{y})\,d\mathbf{y}=\int_{\Gamma_\tau}G_\kappa(\mathbf{x},\mathbf{y})\mu_\tau(\mathbf{y})\,d s_{\mathbf{y}},\qquad\mathbf{x}\in\mathbb{R}^2\setminus\overline{\Omega_\tau}. \tag*{(47)}

Assuming that a unique equivalent density has been selected, define the equivalent-source scattering operator

Fτ:ϕτ↦μτ.(48)F^\tau:\phi_\tau\mapsto\mu_\tau. \tag*{(48)}

For the pure single-layer representation, uniqueness can fail at exceptional Helmholtz frequencies. This issue can be avoided by restricting the box sizes, or by replacing the single-layer representation by an appropriate combined-field representation. Since the present appendix is intended only to record the alternative hierarchical formulation, we do not pursue this question further.

Merge of two adjacent boxes

Consider the same geometry and boundary ordering as in § 3.2:

∂Ωα=Γ1∪Γ3,∂Ωβ=Γ2∪Γ4,Γ3=Γ4,\partial\Omega_\alpha=\Gamma_1\cup\Gamma_3,\qquad\partial\Omega_\beta=\Gamma_2\cup\Gamma_4,\qquad\Gamma_3=\Gamma_4,

and

Γτ=Γ1∪Γ2.\Gamma_\tau=\Gamma_1\cup\Gamma_2.

The parent incoming trace ϕτ\phi_\tau is continued to the complete child boundaries by the same universal operator UτU_\tau used in the field-to-field formulation. Set

φ=Uτϕτ=[φ1φ2φ3φ4].(49)\varphi=U_\tau\phi_\tau= \begin{bmatrix} \varphi_1\\ \varphi_2\\ \varphi_3\\ \varphi_4 \end{bmatrix}. \tag*{(49)}

Let

μ=[μ1μ2μ3μ4]\mu= \begin{bmatrix} \mu_1\\ \mu_2\\ \mu_3\\ \mu_4 \end{bmatrix}

denote the equivalent source densities on the two child boundaries, with

μα=[μ1μ3],μβ=[μ2μ4].\mu_{\alpha} = \begin{bmatrix} \mu_{1} \\ \mu_{3} \end{bmatrix}, \qquad\mu_{\beta} = \begin{bmatrix} \mu_{2} \\ \mu_{4} \end{bmatrix}.

Split the child scattering operators according to their exterior and interface boundary pieces,

Fα=[F11αF13αF31αF33α],Fβ=[F22βF24βF42βF44β],F^{\alpha} = \begin{bmatrix} F^{\alpha}_{11} & F^{\alpha}_{13} \\ F^{\alpha}_{31} & F^{\alpha}_{33} \end{bmatrix}, \qquad F^{\beta} = \begin{bmatrix} F^{\beta}_{22} & F^{\beta}_{24} \\ F^{\beta}_{42} & F^{\beta}_{44} \end{bmatrix},

and form the block operator

F=[F11α0F13α00F22β0F24βF31α0F33α00F42β0F44β].(50)F = \begin{bmatrix} F^{\alpha}_{11} & 0 & F^{\alpha}_{13} & 0 \\ 0 & F^{\beta}_{22} & 0 & F^{\beta}_{24} \\ F^{\alpha}_{31} & 0 & F^{\alpha}_{33} & 0 \\ 0 & F^{\beta}_{42} & 0 & F^{\beta}_{44} \end{bmatrix}. \tag*{(50)}

Thus FF maps the total incoming traces on the two child boundaries to the corresponding equivalent source densities.

The field generated by the sources on one child provides part of the incoming field on its sibling. For example,

\begin{bmatrix} \xi_{1} \\ \xi_{3} \end{bmatrix} = \begin{bmatrix} G_{12} & G_{14} \\ G_{32} & G_{34} \end{bmatrix} \begin{bmatrix} \mu_{2} \\ \mu_{4} \end{bmatrix}, \qquad \begin{bmatrix} \xi_{2} \\ \xi_{4} \end{bmatrix} = \begin{bmatrix} G_{21} & G_{23} \\ G_{41} & G_{43} \end{bmatrix} \begin{bmatrix} \mu_{1} \\ \mu_{3} \end{bmatrix}. \tag*{(51)}\end{bmatrix}

Here ξ\xi denotes the sibling-generated incoming trace. Each operator GijG_{ij} is simply a layer-potential evaluation operator: it maps a single-layer density on Γj\Gamma_j to the value of the resulting field on Γi\Gamma_i. For instance,

[G12μ2](x)=∫Γ2Gκ(x,y)μ2(y) dsy,x∈Γ1.[G_{12}\mu_{2}](\mathbf{x}) = \int_{\Gamma_{2}} G_{\kappa}(\mathbf{x},\mathbf{y})\mu_{2}(\mathbf{y})\,\mathrm{d}s_{\mathbf{y}}, \qquad\mathbf{x} \in\Gamma_{1}.

Combining the two relations in (51) gives

ξ=Gτμ,Gτ=[0G120G14G210G2300G320G34G410G430].(52)\xi= G_{\tau}\mu, \qquad G_{\tau} = \begin{bmatrix} 0 & G_{12} & 0 & G_{14} \\ G_{21} & 0 & G_{23} & 0 \\ 0 & G_{32} & 0 & G_{34} \\ G_{41} & 0 & G_{43} & 0 \end{bmatrix}. \tag*{(52)}

The merge equilibrium equation is therefore

μ=F(φ+Gτμ).(53)\mu= F\left(\varphi+ G_{\tau}\mu\right). \tag*{(53)}

Using (49), we obtain

μ=(I−FGτ)−1FUτϕτ.(54)\mu= \left(I - F G_{\tau}\right)^{-1} F U_{\tau}\phi_{\tau}. \tag*{(54)}

It remains to replace the four child densities in μ\mu by one equivalent density on the parent boundary. Write

μτ=[μ^1μ^2],\mu_{\tau} = \begin{bmatrix} \widehat{\mu}_{1} \\ \widehat{\mu}_{2} \end{bmatrix},

where μ^1\widehat{\mu}_{1} and μ^2\widehat{\mu}_{2} are supported on Γ1\Gamma_{1} and Γ2\Gamma_{2}, respectively. Define the equivalent-source assembly operator VτV_{\tau} by

\begin{bmatrix} \widehat{\mu}_{1} \\ \widehat{\mu}_{2} \end{bmatrix} = \underbrace{\begin{bmatrix} I & 0 & V_{13} & V_{14} \\ 0 & I & V_{23} & V_{24} \end{bmatrix}}_{=:V_{\tau}} \begin{bmatrix} \mu_{1} \\ \mu_{2} \\ \mu_{3} \\ \mu_{4} \end{bmatrix}. \tag*{(55)}\end{bmatrix}

The blocks VijV_{ij} are chosen so that the density μτ=Vτμ\mu_{\tau} = V_{\tau}\mu generates the same field outside Ωτ\Omega_{\tau} as the two child single-layer potentials. Equivalently,

∫ΓτGκ(x,y)μτ(y) dsy=∫∂ΩαGκ(x,y)μα(y) dsy+∫∂ΩβGκ(x,y)μβ(y) dsy,x∈R2∖Ωτ‾.(56)\int_{\Gamma_\tau} G_\kappa(\mathbf{x},\mathbf{y})\mu_\tau(\mathbf{y})\,\mathrm{d}s_{\mathbf{y}} = \int_{\partial\Omega_\alpha} G_\kappa(\mathbf{x},\mathbf{y})\mu_\alpha(\mathbf{y})\,\mathrm{d}s_{\mathbf{y}} + \int_{\partial\Omega_\beta} G_\kappa(\mathbf{x},\mathbf{y})\mu_\beta(\mathbf{y})\,\mathrm{d}s_{\mathbf{y}},\qquad\mathbf{x}\in\mathbb{R}^{2}\setminus\overline{\Omega_\tau}. \tag*{(56)}

Combining (54) and (55) gives the parent scattering operator

Fτ=Vτ(I−FGτ)−1FUτ.(57)F^\tau=V_\tau(I-FG_\tau)^{-1}FU_\tau. \tag*{(57)}

Thus the equivalent-source formulation has the same basic hierarchical structure as the field-to-field method: solve a local multiple-scattering equilibrium between the children, and then replace the pair by a single scattering operator for the parent.

Structure of the merge

The product FGτFG_\tau that appears in (54) has a particularly useful block structure. From (50) and (52),

FGτ=[0F11αG12+F13αG320F11αG14+F13αG34F22βG21+F24βG410F22βG23+F24βG4300F31αG12+F33αG320F31αG14+F33αG34F42βG21+F44βG410F42βG23+F44βG430].(58)FG_\tau= \begin{bmatrix} 0 & F_{11}^{\alpha}G_{12}+F_{13}^{\alpha}G_{32} & 0 & F_{11}^{\alpha}G_{14}+F_{13}^{\alpha}G_{34}\\ F_{22}^{\beta}G_{21}+F_{24}^{\beta}G_{41} & 0 & F_{22}^{\beta}G_{23}+F_{24}^{\beta}G_{43} & 0\\ 0 & F_{31}^{\alpha}G_{12}+F_{33}^{\alpha}G_{32} & 0 & F_{31}^{\alpha}G_{14}+F_{33}^{\alpha}G_{34}\\ F_{42}^{\beta}G_{21}+F_{44}^{\beta}G_{41} & 0 & F_{42}^{\beta}G_{23}+F_{44}^{\beta}G_{43} & 0 \end{bmatrix}. \tag*{(58)}

This identity is useful because almost every term in (58) contains at least one factor that is numerically low rank. The principal exceptions are the terms F33αG34F_{33}^{\alpha}G_{34} and F44βG43F_{44}^{\beta}G_{43}, which couple the two copies of the common interface. These blocks are not globally low rank, but they have multilevel rank structure. Thus, just as in the field-to-field formulation, the merge contains considerable exploitable structure even though the present appendix does not attempt to use it.

Remark 5 (Comparison with the field-to-field formulation). The two formulations use the same incoming trace and the same local Lippmann–Schwinger solves. Their difference is entirely in the representation of the outgoing field. In the formulation used in the main text, the outgoing state is the boundary trace ψτ\psi_\tau. This avoids equivalent-source reconstruction and makes the coupling across the common interface particularly simple: two blocks of EτE_\tau are identities. In the present formulation, the outgoing state is the single-layer density μτ\mu_\tau. Propagation between children is then given directly by the universal single-layer evaluation operator GτG_\tau, but the near-field blocks G34G_{34} and G43G_{43} require singular or nearly singular layer-potential evaluation, and the parent merge requires the additional equivalent-source reconstruction VτV_\tau. These considerations are the main reasons that the field-to-field formulation was preferred in the implementation described in this paper.

Remark 6 (Universal operators). The interaction operator GτG_\tau and the assembly operator VτV_\tau are independent of the scattering potential bb, as is the incoming continuation operator UτU_\tau. They depend only on the geometry and on the free-space Helmholtz operator, and can therefore be precomputed. The separated-boundary blocks of GτG_\tau are smoothing and highly compressible. The interface blocks G34G_{34} and G43G_{43} require near-field evaluation and, at high accuracy, a multilevel representation. These observations provide a possible alternative route to accelerating the method if the equivalent-source formulation is revisited in future work.

References

  1. [1]J. C. Aguilar and Yu Chen, A high-order, fast algorithm for scattering calculation in two dimensions, Computers & Mathematics with Applications 47 (2004), no. 1, 1–11.
  2. [2]Sivaram Ambikasaran, Carlos Borges, Lise-Marie Imbert-Gerard, and Leslie Greengard, Fast, adaptive, high-order accurate discretization of the Lippmann–Schwinger equation in two dimensions, SIAM Journal on Scientific Computing 38 (2016), no. 3, A1770–A1787.DOI
  3. [3]Akash Anand, Ambuj Pandey, B. V. Rathish Kumar, and Jagabandhu Paul, An efficient high-order Nyström scheme for acoustic scattering by inhomogeneous penetrable media with discontinuous material interface, Journal of Computational Physics 311 (2016), 258–274.DOI
  4. [4]Travis Askham, Manas Rachh, Michael O’Neil, Jeremy Hoskins, Dan Fortunato, and Shidong Jiang, chunkie: a matlab integral equation toolbox, https://github.com/fastalgorithms/chunkie, 2023.
  5. [5]Mario Bebendorf, Hierarchical matrices, Lecture Notes in Computational Science and Engineering, vol. 63, Springer-Verlag, Berlin, 2008, A means to efficiently solve elliptic boundary value problems. MR 2451321 (2009k:15001)DOI
  6. [6]Carlos Borges, Adrianna Gillman, and Leslie Greengard, High resolution inverse scattering in two dimensions using recursive linearization, SIAM Journal on Imaging Sciences 10 (2017), no. 2, 641–664.arxiv.org/abs/1608.06871
  7. [7]Duan Chen, Min Hyung Cho, and Wei Cai, Accurate and efficient Nyström volume integral equation method for electromagnetic scattering of 3-d metamaterials in layered media, SIAM Journal on Scientific Computing 40 (2018), no. 1, B259–B282.DOI
  8. [8]Yu Chen, A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions, Adv. Comput. Math. 16 (2002), no. 2-3, 175–190, Modeling and computation in optics and electromagnetics. MR 1892248 (2003b:65139)DOI
  9. [9]Weng Cho Chew, Levent Gurel, Y-M Wang, Gregory Otto, Robert L Wagner, and Qing Huo Liu, A generalized recursive algorithm for wave-scattering solutions in two dimensions, IEEE transactions on microwave theory and techniques 40 (1992), no. 4, 716–723.DOI
  10. [10]Weng Cho Chew and Cai-Cheng Lu, The use of Huygens’ equivalence principle for solving the volume integral equation of scattering, IEEE Transactions on Antennas and Propagation 41 (1993), no. 7, 897–904.DOI
  11. [11]Weng Cho Chew and Y. M. Wang, Reconstruction of two-dimensional permittivity distribution using the distorted Born iterative method, IEEE Transactions on Medical Imaging 9 (1990), no. 2, 218–225.pubmed.ncbi.nlm.nih.gov/18222767
  12. [12]David Colton and Rainer Kress, Integral equation methods in scattering theory, vol. 72, SIAM, 2013.DOI
  13. [13][——— , Inverse acoustic and electromagnetic scattering theory, 4 ed., Applied Mathematical Sciences, vol. 93, Springer, Cham, 2019.
  14. [14]Eduardo Corona, Per-Gunnar Martinsson, and Denis Zorin, An o (n) direct solver for integral equations on the plane, Applied and Computational Harmonic Analysis 38 (2015), no. 2, 284–317.arxiv.org/abs/1303.5466
  15. [15]Ran Duan and Vladimir Rokhlin, High-order quadratures for the solution of scattering problems in two dimensions, J. Comput. Physics 228 (2009), no. 6, 2152–2174.
  16. [16]Benjamin Fuchs, Sébastien Palud, Laurent Le Coq, Olivier Lafond, Mohamed Himdi, and Sébastien Rondineau, Scattering of spherically and hemispherically stratified lenses fed by any real source, IEEE Transactions on Antennas and Propagation 56 (2008), no. 2, 450–460.DOI
  17. [17]M. Ganesh, S. C. Hawkins, and R. Hiptmair, Convergence analysis with parameter estimates for a reduced basis acoustic scattering T-matrix method, IMA Journal of Numerical Analysis 32 (2012), no. 4, 1348–1374.DOI
  18. [18]M. Ganesh and S.C. Hawkins, A fast high order algorithm for multiple scattering from large sound-hard three dimensional configurations, Journal of Computational and Applied Mathematics 362 (2019), 324 – 340.DOI
  19. [19]M. Ganesh, J.S. Hesthaven, and B. Stamm, A reduced basis method for electromagnetic scattering by multiple particles in three dimensions, Journal of Computational Physics 231 (2012), no. 23, 7756–7779.DOI
  20. [20]A. Gillman and P. Martinsson, A direct solver with o(n) complexity for variable coefficient elliptic pdes discretized via a high-order composite spectral collocation method, SIAM Journal on Scientific Computing 36 (2014), no. 4, A2023–A2046, arXiv.org report #1307.2665.arxiv.org/abs/1307.2665
  21. [21]Adrianna Gillman, Alex H. Barnett, and Per-Gunnar Martinsson, A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media, BIT Numerical Mathematics 55 (2015), no. 1, 141–170.arxiv.org/abs/1308.5998
  22. [22]Abinand Gopal and Per-Gunnar Martinsson, An accelerated, high-order accurate direct solver for the Lippmann–Schwinger equation for acoustic scattering in the plane, Advances in Computational Mathematics 48 (2022), no. 4, 1–31.arxiv.org/abs/2007.12718
  23. [23]Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of ℋ-matrices, Computing 70 (2003), no. 4, 295–334.DOI
  24. [24]L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348.
  25. [25]Johan Helsing, Solving Integral Equations on Piecewise Smooth Boundaries Using the RCIP Method: A Tutorial, Abstract and Applied Analysis 2013 (2013), no. SI51, 1 – 20.
  26. [26]Yushin Kim, Soo-Young Lee, Jung-Wan Ryu, Inbo Kim, Jae-Hyung Han, Heung-Sik Tae, Muhan Choi, and Bumki Min, Designing whispering gallery modes via transformation optics, Nature Photonics 10 (2016), no. 10, 647–652.
  27. [27]Philip Trøst Kristensen, Peter Lodahl, and Jesper Mørk, Light propagation in finite-sized photonic crystals: multiple scattering using an electric field integral equation, Journal of the Optical Society of America B 27 (2010), no. 2, 228–237.arxiv.org/abs/0908.4240
  28. [28]Fei Liu and Lexing Ying, Sparsify and sweep: An efficient preconditioner for the Lippmann–Schwinger equation, SIAM Journal on Scientific Computing 40 (2018), no. 2, B379–B404.arxiv.org/abs/1705.09443
  29. [29]P.G. Martinsson, A direct solver for variable coefficient elliptic pdes discretized via a composite spectral collocation method, Journal of Computational Physics 242 (2013), no. 0, 460 – 479.DOI
  30. [30]P.G. Martinsson and V. Rokhlin, A fast direct solver for boundary integral equations in two dimensions, J. Comp. Phys. 205 (2005), no. 1, 1–23.
  31. [31]Hossein Mosallaei and Yahya Rahmat-Samii, Nonuniform Luneburg and two-shell lens antennas: Radiation characteristics and design optimization, IEEE Transactions on Antennas and Propagation 49 (2001), no. 1, 60–69.DOI
  32. [32]Neslihan Ozmen, Robin Dapp, Michael Zapf, Hartmut Gemmeke, Nicole V Ruiter, and Koen WA Van Dongen, Comparing different ultrasound imaging methods for breast cancer detection, IEEE transactions on ultrasonics, ferroelectrics, and frequency control 62 (2015), no. 4, 637–646.DOI
  33. [33]V. Rokhlin, Rapid solution of integral equations of scattering theory in two dimensions, J. Comput. Phys. 86 (1990), 414–439.
  34. [34]John R. Sanford, Scattering by spherically stratified microwave lens antennas, IEEE Transactions on Antennas and Propagation 42 (1994), no. 5, 690–698.DOI
  35. [35]Mirbek Turduev, E Bor, and Hamza Kurt, Photonic crystal based polarization insensitive flat lens, Journal of Physics D: Applied Physics 50 (2017), no. 27, 275105.DOI
  36. [36]Zhun Wei and Xudong Chen, Deep-learning schemes for full-wave nonlinear inverse scattering problems, IEEE Transactions on Geoscience and Remote Sensing 57 (2019), no. 4, 1849–1860.DOI
  37. [37]Lexing Ying, Sparsifying preconditioner for the Lippmann–Schwinger equation, Multiscale Modeling & Simulation 13 (2015), no. 2, 644–660.arxiv.org/abs/1408.4495
  38. [38]Lexing Ying, George Biros, and Denis Zorin, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, Journal of Computational Physics 196 (2004), no. 2, 591–626.
  39. [39]Leonardo Zepeda-Nuñez and Hongkai Zhao, Fast alternating bidirectional preconditioner for the 2d high-frequency Lippmann–Schwinger equation, SIAM Journal on Scientific Computing 38 (2016), no. 5, B866–B888.

Paper details

vlnc:W_8ttcnh7m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents