betaFeedback

WorksMathematics

Accelerated Born series for high-frequency strong scattering by weakly non-radial media

Abstract

We present a practical method for accelerating the modified Born series for high-frequency Helmholtz scattering in one, two, and three dimensions. We consider bounded, nonnegative, compactly supported media, allowing small departures from radial symmetry in two and three dimensions. The method selects a single complex relaxation parameter using an approximation of the scattering operator's spectrum. Starting from precomputed eigenvalues for a constant reference medium, we estimate their evolution towards the prescribed radial profile. A leading-order Wentzel-Kramers-Brillouin (WKB) approximation reduces this spectral propagation to scalar nonlinear equations, followed by a first-order correction for the nonradial part of the medium. The estimated eigenvalues, together with a bound on the omitted spectrum, define a convex minimax problem for selecting the relaxation parameter. This spectral preparation is independent of the source and can therefore be reused for multiple scattering problems in the same medium. Numerical examples demonstrate convergence in strongly scattering cases where the scattering operator has spectral radius greater than one. Comparisons with direct integral-equation and finite-difference solvers assess accuracy, residual convergence, and computation time, and show computational savings at comparable accuracy in selected examples.

Introduction

We here consider scattering problems in dimension d=1,2,3d=1,2,3 at a fixed positive frequency (wavenumber) kk. For the case d=1d=1, fix a positive length LL, a bounded and piecewise C1C^1 medium function qq supported in [0,L][0,L], with

q(x)≥0,lim⁡x→0q(x)≠0,lim⁡x→Lq(x)≠0,q(x) \ge0,\qquad\lim_{x\to0}q(x) \ne0,\qquad\lim_{x\to L}q(x) \ne0,

as well as a source f∈L2(R)f\in L^2(\mathbb{R}) supported in [0,L][0,L]. The scattering problem is then

{u′′+k2(1+q(x))u=−f,x∈(0,L),−u′(0)=iku(0),u′(L)=iku(L).(1)\begin{cases} u''+k^2(1+q(x))u=-f,\quad x\in(0,L),\\ -u'(0)=iku(0),\\ u'(L)=iku(L). \tag*{(1)} \end{cases}

For the case d∈{2,3}d \in\{2,3\}, let BR={x∈Rd, ∣x∣<R}B_R=\{x\in\mathbb{R}^d,\ |x|<R\} for some positive RR, and fix a nonnegative-valued, bounded, and piecewise C1C^1 medium function qq supported in BR‾\overline{B_R}, with lim⁡r↗Rq(rω)≠0\lim_{r\nearrow R}q(r\omega)\ne0 for ω∈Sd−1\omega\in S^{d-1}, as well as a source f∈L2(Rd)f\in L^2(\mathbb{R}^d) supported in BR‾\overline{B_R}. Assume furthermore that qq is ’weakly non-radial’, i.e., such that

q(x)=qrad(∣x∣)+ηQ(x),q(x)=q_{\mathrm{rad}}(|x|)+\eta Q(x),

with the radial part

qrad(r)=1∣Sd−1∣∫ω∈Sd−1q(rω) dω,r∈[0,R],q_{\mathrm{rad}}(r)=\frac{1}{\lvert S^{d-1}\rvert}\int_{\omega\in S^{d-1}}q(r\omega)\,d\omega,\qquad r\in[0,R],

and the perturbation ∥Q∥∞=1\lVert Q\rVert_\infty=1, ∣η∣≪1\lvert\eta\rvert\ll1. The scattering problem is then

{[Δ+k2(1+q(x))]u=−f,x∈Rd,lim⁡∣x∣→∞∣x∣(d−1)/2(∂∣x∣u−iku)=0,uniformly in x/∣x∣∈Sd−1.(2)\begin{cases} \left[\Delta+k^2(1+q(x))\right]u=-f, & x\in\mathbb{R}^d,\\ \lim_{\lvert x\rvert\to\infty}\lvert x\rvert^{(d-1)/2}(\partial_{\lvert x\rvert}u-iku)=0, & \text{uniformly in }x/\lvert x\rvert\in S^{d-1}. \tag*{(2)} \end{cases}

In the following define the domain D=(0,L)D=(0,L) when d=1d=1 and D=BRD=B_R when d∈{2,3}d\in\{2,3\}. The problems (1) and (2) are posed in the usual outgoing weak sense, each PDE being supplied with the dimension-specific Sommerfeld radiation condition. The solution uu satisfies u∣D∈L2(D)u|_D\in L^2(D), and it is the total field resulting from the illumination of the medium qq by the source ff.

We are here concerned with the practical solvability of (1) and (2) in terms of the modified Born series (MBS) introduced by Kleinman et al. [7–10],

u=∑n=0∞[Mγ(k)]nγV1(k)f,(3)u=\sum_{n=0}^{\infty}[M_\gamma(k)]^{n\gamma}V_1(k)f, \tag*{(3)}

where Mγ(k)=(1−γ)I+γk2Vq(k)M_\gamma(k)=(1-\gamma)I+\gamma k^2V_q(k), the constant γ∈C\gamma\in\mathbb{C} is the so-called preconditioner or overrelaxation parameter, and V1(k)V_1(k), Vq(k)V_q(k) are the standard radiating volume potentials,

Va(k)u(x)=∫DΦk(d)(x−y)a(y)u(y) dy,V_a(k)u(x)=\int_D\Phi_k^{(d)}(x-y)a(y)u(y)\,dy,

with

Φk(1)(x)=i2keik∣x∣,Φk(2)(x)=i4H0(1)(k∣x∣),andΦk(3)(x)=eik∣x∣4π∣x∣,\Phi_k^{(1)}(x)=\frac{i}{2k}e^{ik|x|},\qquad\Phi_k^{(2)}(x)=\frac{i}{4}H_0^{(1)}(k|x|),\qquad\text{and}\qquad\Phi_k^{(3)}(x)=\frac{e^{ik|x|}}{4\pi|x|},

the unique outgoing fundamental solution of the Helmholtz operator Δ+k2\Delta+k^2 in Rd\mathbb{R}^d for $d=1,2,3. Here H0(1)H_0^{(1)} is the Hankel function of the first kind and order zero.

Convolving the PDE in (1) or in (2) with the outgoing fundamental solution, and integrating by parts, we get the Lippmann-Schwinger integral equation

(I−k2Vq(k))u=V1(k)f,in D.(4)(I-k^2V_q(k))u=V_1(k)f,\qquad\text{in }D. \tag*{(4)}

It is well-known [5, Section 2] that the integral equation (4) is equivalent with (1)-(2). Recall [3] that the mapping Vq(k):L2(D)→L2(D)V_q(k):L^2(D)\to L^2(D) is compact, and that the Fredholm equation of the second kind (4) has a unique solution u=u= (I−k2Vq(k))−1V1(k)f(I-k^2V_q(k))^{-1}V_1(k)f. If the spectral radius ϱ(k2Vq(k))\varrho(k^2V_q(k)) of k2Vq(k)k^2V_q(k) is less than one then the solution of the integral equation is given by the Born series

u=∑n=0∞[k2Vq(k)]n(V1(k)f).u=\sum_{n=0}^{\infty}[k^2V_q(k)]^n(V_1(k)f).

In [13, Lemma 5] we proved, for scattering problem dimensions d=1,2,3d=1,2,3 and general bounded media qq, the existence of γ\gamma that ensures the convergence of the modified Born series (3) regardless of the value of the spectral radius ϱ(k2Vq(k))\varrho(k^2V_q(k)), that is, including the strong scattering case (large ∥q∥∞\lVert q\rVert_\infty) and the high-frequency case (large kk). Moreover, in [13, Lemma 6] we provided a practically calculable sufficient condition for such γ\gamma in dimension d=1d=1 with q(x)=∥q∥∞1[0,L](x)q(x)=\lVert q\rVert_\infty\mathbf{1}_{[0,L]}(x).

Ideally, we estimate the optimal preconditioner parameter γopt\gamma_{\mathrm{opt}} by minimizing the spectral radius of Mγ(k)M_\gamma(k); in practice, we solve the minimax problem (16) using the estimated spectrum. The aim is to improve the worst-case asymptotic convergence rate of the MBS (3) and thereby reduce the number of terms needed to reach a prescribed tolerance. To this end, we estimate in Section 2 the spectral evolution of the operator k2Vqt(k)k^2V_{q_t}(k) for the homotopy

qt=(1−t)∥q∥∞1D+tqrad,t∈[0,1],q_t=(1-t)\lVert q\rVert_\infty\mathbf{1}_D+tq_{\mathrm{rad}},\qquad t\in[0,1],

followed by a correction, to first order in η\eta, of the computed eigenvalues λj(1)\lambda_j(1) from those of k2Vqrad(k)k^2V_{q_{\mathrm{rad}}}(k) to those of k2Vq(k)k^2V_q(k); recall that we assume q(x)=qrad(∣x∣)+ηQ(x)q(x)=q_{\mathrm{rad}}(\lvert x\rvert)+\eta Q(x) with ∥Q∥∞=1\lVert Q\rVert_\infty=1 and with small η\eta. To leading order in a WKB approximation [2], the spectral evolution of k2Vqt(k)k^2V_{q_t}(k) from t=0t=0 to t=1t=1 can be computed by solving a collection of scalar nonlinear equations for the endpoint eigenvalues. In Section 3, we use the estimated spectrum of k2Vq(k)k^2V_q(k) to arrive at inexpensive numerical estimates of γopt\gamma_{\mathrm{opt}}. In Section 4, we present numerical examples of the application of our accelerated MBS solver, including validation against direct solvers.

Our proposed workflow is thus as follows:

  1. Pre-compute eigenvalues λj(0)\lambda_j(0), j=1,…,Jj=1,\ldots,J, of k2Vq0(k)k^2V_{q_0}(k) for the values kk, ∥q∥∞\lVert q\rVert_\infty, and ∣D∣\lvert D\rvert of interest.

  1. Given a specific medium q=qrad+ηQq=q_{\mathrm{rad}}+\eta Q of interest, propagate the selected eigenvalue branches for k2Vqt(k)k^2V_{q_t}(k), with qt=(1−t)q0+tqradq_t=(1-t)q_0+tq_{\mathrm{rad}}, from t=0t=0 to t=1t=1 using the high-frequency spectral-evolution equation (7). This reduces to the solution of JJ scalar nonlinear equations, as specified in (9) for d=1d=1, in (11) for d=2d=2, and in (13) for d=3d=3.

  1. If the medium qq is nonradial (η≠0\eta\ne0) then correct the computed λj(1)\lambda_j(1), j=1,…,Jj=1,\ldots,J, using (15).

  1. Use the (corrected) λj(1)\lambda_j(1), j=1,…,Jj=1,\ldots,J, to estimate γopt\gamma_{\mathrm{opt}}.

  1. For each error tolerance ε\varepsilon and each specific source ff of interest, compute

uMBS=∑n=0N(ε)[Mγopt(k)]nγoptV1(k)f.u_{\mathrm{MBS}}=\sum_{n=0}^{N(\varepsilon)}[M_{\gamma_{\mathrm{opt}}}(k)]^n\gamma_{\mathrm{opt}}V_1(k)f.

Step 1 encompasses a large class of media, as well as all sources. Steps 2–4 encompass all sources for a given medium. Thus, if we for example consider scattering by a fixed medium excited by ν\nu different sources then the required computations reduce to a small fixed overhead (steps 1–4), followed by ν×(N(ε)+1)\nu\times(N(\varepsilon)+1) matrix-vector multiplications and ν×N(ε)\nu\times N(\varepsilon) vector summations. The most computationally intensive part is thus well-suited for GPU implementation.

The systems (1)-(2) arise in the time-harmonic case, with the time-dependence factor e−iωte^{-i\omega t}, of the initial-value problem for the scalar wave equation

{utt−c2(x)Δu=0,u(x,0)=0,∂tu(x,0)=c2f,\begin{cases} u_{tt}-c^{2}(x)\Delta u = 0,\\ u(x,0) = 0,\\ \partial_tu(x,0) = c^{2}f, \end{cases}

where the medium function is given by q=c02/c2−1q=c_{0}^{2}/c^{2}-1, with c0>0c_{0}>0 being the ambient constant wavespeed, c(x)>0c(x)>0 the variable wavespeed describing the scatterer, and k=ω/c0k=\omega/c_{0}.

Kleinman et al. [7–10] devised the modified Born series by introducing an overrelaxation of the original Lippmann-Schwinger equation (I−k2Vq(k))u=ψ(I-k^{2}V_{q}(k))u=\psi in terms of the equivalent equation (I−Mγ(k))u=γψ(I-M_{\gamma}(k))u=\gamma\psi with Mγ(k)=(1−γ)I+γk2Vq(k)M_{\gamma}(k)=(1-\gamma)I+\gamma k^{2}V_{q}(k), and where γ∈C\gamma\in\mathbb{C} is the overrelaxation parameter (see also [4]).

For scattering configurations in dimensions d=1,2,3d=1,2,3 and involving piecewise Hölder continuous contrasts, they proved the existence of complex constants γ\gamma for which the modified Born series u=∑n=0∞[Mγ(k)]nγψu=\sum_{n=0}^{\infty}[M_{\gamma}(k)]^{n}\gamma\psi converges, as well as a sufficient condition for the choice of overrelaxation parameter resulting in convergent modified Born series. However, this sufficient condition involves parameters defining the geometry of the spectrum of the operator k2Vq(k)k^{2}V_{q}(k), making the result less readily applicable in practice. Kleinman et al. [10] therefore also supplied an empirical recipe for the choice of the overrelaxation parameter, as well as some supporting numerical evidence. More recently, Osnabrugge et al. [11] devised a more elaborate approach, with a non-constant function (’pre-conditioner’ γ(x)\gamma(x)) taking the place of the overrelaxation parameter, and using operators of the form F−1g~0FF^{-1}\widetilde{g}_{0}F, with F,F−1F,F^{-1} the Fourier transform and its inverse, respectively, and g~0\widetilde{g}_{0} the Fourier transform of the outgoing fundamental solution of the Helmholtz operator in Rd\mathbb{R}^{d} at a complex frequency k02+iεk_{0}^{2}+i\varepsilon. The added numerical complexity of this approach pays off in that the function γ(x)\gamma(x) is well-known from the outset and it is therefore not required to estimate a good overrelaxation parameter. Finally, Stanziola et al. [12] used machine learning to arrive at Learned Born Series (LBS), speeding up the convergence of the MBS from [11] for strongly scattering media.

WKB approximation of the spectral evolution

In this section we describe the two distinct steps outlined in Section 1, namely the spectral propagation of k2Vqt(k)k^{2}V_{q_t}(k) for qt=(1−t)q0+tqradq_t=(1-t)q_0+tq_{\mathrm{rad}}, t∈[0,1]t\in[0,1], and the subsequent first-order correction of the spectrum of k2Vqrad(k)k^{2}V_{q_{\mathrm{rad}}}(k) to that of k2Vq(k)k^{2}V_q(k), where q(x)=qrad(∣x∣)+ηQ(x)q(x)=q_{\mathrm{rad}}(|x|)+\eta\mathcal{Q}(x) with qradq_{\mathrm{rad}} radial, ∥Q∥∞=1\|\mathcal{Q}\|_{\infty}=1, and η\eta small.

Spectral propagation

Given a medium qq as described in § 1, write q0=∥q∥∞1Dq_0=\lVert q\rVert_{\infty1D} and consider the homotopy

qt=(1−t)q0+tqrad,t∈[0,1].(5)q_t=(1-t)q_0+tq_{\mathrm{rad}},\qquad t\in[0,1]. \tag*{(5)}

Note that, for all t∈[0,1]t\in[0,1], we have qt(x)≥0q_t(x)\ge0 and qtq_t is nowhere vanishing at ∂D\partial D. We are interested in the one-parameter family of eigenvalue problems

k2Vqt(k)φt=λ(t)φt,t∈[0,1].(6)k^2V_{q_t}(k)\varphi_t=\lambda(t)\varphi_t,\qquad t\in[0,1]. \tag*{(6)}

Specifically, we seek the variation of eigenvalue branches λ(t)\lambda(t) along the homotopy qtq_t, t∈[0,1]t\in[0,1]. Since Vqt(k)=Vq0(k)+tVqrad−q0(k)V_{q_t}(k)=V_{q_0}(k)+tV_{q_{\mathrm{rad}}-q_0}(k) is tt-analytic, λ(t)\lambda(t) is piecewise analytic, with at most finitely many exceptional points [1] [6]. In dimension d=1d=1 the eigenvalues are geometrically simple because of the Robin boundary condition at x=0x=0. Indeed, assume φt(j)\varphi_t^{(j)}, j=1,2j=1,2, are two eigenfunctions corresponding to the same eigenvalue λ(t)\lambda(t), with φt(j)(0)=aj\varphi_t^{(j)}(0)=a_j. Then a1≠0a_1\ne0 and a2≠0a_2\ne0, and

φt(1)(0)=a1a2φt(2)(0)and(φt(1))′(0)=a1a2(φt(2))′(0),\varphi_t^{(1)}(0)=\frac{a_1}{a_2}\varphi_t^{(2)}(0)\qquad\text{and}\qquad\left(\varphi_t^{(1)}\right)'(0)=\frac{a_1}{a_2}\left(\varphi_t^{(2)}\right)'(0),

so that φt(1)=(a1/a2)φt(2)\varphi_t^{(1)}=(a_1/a_2)\varphi_t^{(2)}. In dimensions d=2,3d=2,3, the reference medium q0q_0 is radial, and the corresponding Helmholtz operator Δ+k2(1+q0/λ(0))\Delta+k^2(1+q_0/\lambda(0)) is rotationally invariant. Hence its eigenspaces decompose into angular Fourier modes in d=2d=2 and spherical harmonics in d=3d=3. For d=2d=2, the modes are labeled by m∈Zm\in\mathbb{Z}, and for d=3d=3 they are labeled by the angular momentum ℓ∈N0\ell\in\mathbb{N}_0. For d=2d=2 the eigenvalues have multiplicity 1 when m=0m=0 and 2 when m≠0m\ne0, and for d=3eachcorrespondingeigenvaluecarriesthemultiplicity$2ℓ+1d=3 each corresponding eigenvalue carries the multiplicity \$2\ell+1. Since qradq_{\mathrm{rad}} is radial, these multiplicities are preserved along the homotopy. Taking variations of (6), we get

k2Vqt+δq(k)(φt+δφ)=(λ(t)+δλ)(φt+δφ),k^2V_{q_t+\delta q}(k)(\varphi_t+\delta\varphi)=(\lambda(t)+\delta\lambda)(\varphi_t+\delta\varphi),

so, to leading order, we have

k2Vqt(k)δφ+k2Vδq(k)φt=λ(t)δφ+δλφt.k^2V_{q_t}(k)\delta\varphi+k^2V_{\delta q}(k)\varphi_t=\lambda(t)\delta\varphi+\delta\lambda\varphi_t.

Now use the bilinear pairing ⟨u,v⟩=∫Du(x)v(x)dx\langle u,v\rangle=\int_Du(x)v(x)dx and consider the transpose (k2Vqt(k))T(k^2V_{q_t}(k))^T, defined by ⟨k2Vqt(k)u,v⟩=⟨u,(k2Vqt(k))Tv⟩\langle k^2V_{q_t}(k)u,v\rangle=\langle u,(k^2V_{q_t}(k))^Tv\rangle. We readily check that the eigenvalues and eigenvectors of (k2Vqt(k))T(k^2V_{q_t}(k))^T are given by λ(t)\lambda(t) and qtφtq_t\varphi_t, respectively: writing the multiplication operator Qqt=qt⋅(⋅)Q_{q_t}=q_t\cdot(\cdot), and K(k)=k2∫DΦk(d)(x−y)(⋅)(y)dyK(k)=k^2\int_D\Phi_k^{(d)}(x-y)(\cdot)(y)dy, we have QqtT=QqtQ_{q_t}^T=Q_{q_t} and K(k)T=K(k)K(k)^T=K(k), so k2Vqt(k)φt=λ(t)φtk^2V_{q_t}(k)\varphi_t=\lambda(t)\varphi_t implies

(k2Vqt(k))T(qtφt)=QqtK(k)(qtφt)=Qqtk2Vqt(k)φt=λ(t)qtφt.(k^2V_{q_t}(k))^T(q_t\varphi_t)=Q_{q_t}K(k)(q_t\varphi_t)=Q_{q_t}k^2V_{q_t}(k)\varphi_t=\lambda(t)q_t\varphi_t.

Furthermore, we have δq=(qrad−q0)δt\delta q=(q_{\mathrm{rad}}-q_0)\delta t for every t∈(0,1)t\in(0,1), so

δt⟨k2Vqrad−q0(k)φt,qtφt⟩=⟨k2Vδq(k)φt,qtφt⟩=δλ⟨φt,qtφt⟩,\delta t\langle k^2V_{q_{\mathrm{rad}}-q_0}(k)\varphi_t,q_t\varphi_t\rangle=\langle k^2V_{\delta q}(k)\varphi_t,q_t\varphi_t\rangle=\delta\lambda\langle\varphi_t,q_t\varphi_t\rangle,

which leads to

λ′(t)=⟨k2Vqrad−q0(k)φt,qtφt⟩⟨φt,qtφt⟩=λ(t)∫D(qrad(x)−q0(x))φt2(x)dx∫Dqt(x)φt2(x)dx,t∈(0,1),\lambda'(t)=\frac{\langle k^2V_{q_{\mathrm{rad}}-q_0}(k)\varphi_t,q_t\varphi_t\rangle}{\langle\varphi_t,q_t\varphi_t\rangle} =\lambda(t)\frac{\int_D(q_{\mathrm{rad}}(x)-q_0(x))\varphi_t^2(x)dx}{\int_Dq_t(x)\varphi_t^2(x)dx},\qquad t\in(0,1),

or equivalently

ddtlog⁡λ(t)=∫D(qrad(x)−q0(x))φt2(x) dx∫Dqt(x)φt2(x) dx,t∈(0,1).(7)\frac{d}{dt}\log\lambda(t)=\frac{\int_D(q_{\mathrm{rad}}(x)-q_0(x))\varphi_t^2(x)\,dx}{\int_D q_t(x)\varphi_t^2(x)\,dx},\qquad t\in(0,1). \tag*{(7)}

We do not have a formal justification for the division by ∫Dqtφt2 dx\int_D q_t\varphi_t^2\,dx; instead, we shall assume this division is well-defined, and rely on numerical examples to check the practical applicability of the approach. The idea now is to start with the eigenvalues of k2Vq0(k)k^2V_{q_0}(k), at t=0t=0, which is a canonical case, and then to propagate these eigenvalues to those of k2Vqrad(k)k^2V_{q_{\mathrm{rad}}}(k), at t=1t=1, using the ODE (7). This of course requires some knowledge of the point spectrum of k2Vq0(k)k^2V_{q_0}(k), as well as of the eigenfunctions φt\varphi_t for t∈[0,1]t\in[0,1]. In what follows, we shall approximate the eigenfunctions φt\varphi_t using the high-frequency Wentzel–Kramers–Brillouin (WKB, [2]) formalism. Regarding the eigenvalues of k2Vq0(k)k^2V_{q_0}(k), a finite representative number of these can be computed numerically once and for all for the contrast ∥q∥∞,1D\lVert q\rVert_{\infty,1D} and the size parameter κ=kL\kappa=kL (d=1d=1) or κ=kR\kappa=kR (d=2,3d=2,3) of interest, or they can be estimated semi-analytically. In dimension d=1d=1, for example, we already have an explicit parametrization [13, proof of Proposition 3] of the curve Λ0\Lambda_0 on which the eigenvalues λj(0)\lambda_j(0) of k2Vq0(k)k^2V_{q_0}(k) reside, namely

Λ0={∥q∥∞s2−1, s∈S−∪S+},\Lambda_0=\left\{\frac{\lVert q\rVert_\infty}{s^2-1},\ s\in S_-\cup S_+\right\},

with

S±={−cosh⁡κt±1−t2sinh⁡2κtsinh⁡κt+it, t∈(0,T]},S_\pm=\left\{\frac{-\cosh\kappa t\pm\sqrt{1-t^2\sinh^2\kappa t}}{\sinh\kappa t}+it,\ t\in(0,T]\right\},

and Tsinh⁡(κT)=1T\sinh(\kappa T)=1. In dimensions d=2d=2 and d=3d=3, we could attempt to find curves in C\mathbb{C} that envelop the point spectrum σp(k2Vq0(k))\sigma_p(k^2V_{q_0}(k)) by solving transcendental equations involving (spherical) Bessel and Hankel functions. Instead of this approach, however, we here opt for the one-off numerical computation of a finite number of eigenvalues of k2Vq0(k)k^2V_{q_0}(k) for all d∈{1,2,3}d\in\{1,2,3\}.

We do not in general have an analytic expression of φt\varphi_t for t∈(0,1]t\in(0,1]. To continue the analysis of (7), we first note that the eigenvalue problem (6) is equivalent with the variable-coefficient Helmholtz system

{[Δ+k2(1+qt(x)/λ(t))]φt=0,x∈D,+ Sommerfeld radiation condition,(8)\begin{cases} \left[\Delta+k^2(1+q_t(x)/\lambda(t))\right]\varphi_t=0,\qquad x\in D,\\ +\ \text{Sommerfeld radiation condition}, \tag*{(8)} \end{cases}

which has a nontrivial solution only if ℑλ(t)>0\Im\lambda(t)>0, that is, only in the case of an exponentially unstable (active medium) wave equation – see, e.g., the proof of Lemma 5 in [13]. Then, in what follows, we will use the high-frequency (k≫1k\gg1) WKB ansatz [2] to arrive at approximate solutions of (8).

Case d=1d=1

Now first let d=1d=1 and q=qrad∈C1([0,L])q=q_{\mathrm{rad}}\in C^1([0,L]). For piecewise C1C^1 contrasts, the WKB construction is understood on each smooth subinterval. Interface matching terms may generate additional reflected and transmitted contributions; these are here neglected at the leading averaged level. In one dimension we have only two rays, and the system (8) is readily solvable to leading order in kk, giving

φt2(x)≈c12(t)e2ikSt,1(x)+c22(t)e−2ikSt,1(x)+2c1(t)c2(t)(1+qt(x)/λ(t))1/2,\varphi_t^2(x)\approx\frac{c_1^2(t)e^{2ikS_{t,1}(x)}+c_2^2(t)e^{-2ikS_{t,1}(x)}+2c_1(t)c_2(t)}{(1+q_t(x)/\lambda(t))^{1/2}},

with

St,j(x)=(−1)j+1∫0x(1+qt(y)/λ(t))1/2 dy,at,j(x)=cj(t)(1+qt(x)/λ(t))1/4,j=1,2.S_{t,j}(x)=(-1)^{j+1}\int_0^x(1+q_t(y)/\lambda(t))^{1/2}\,\mathrm{d}y,\qquad a_{t,j}(x)=\frac{c_j(t)}{(1+q_t(x)/\lambda(t))^{1/4}},\qquad j=1,2.

Assuming that the WKB phases have no stationary points on (0,L)(0,L), that the relevant branch of St,1S_{t,1} has controlled imaginary part, and that the oscillatory terms are negligible after high-frequency averaging, we obtain formally, after substitution into (7), and to leading order as k→∞k\to\infty, that

λ′(t)λ(t)=∫0Lqrad(x)−q0(x)(1+qt(x)/λ(t))1/2 dx∫0Lqt(x)(1+qt(x)/λ(t))1/2 dx.\frac{\lambda'(t)}{\lambda(t)}= \frac{\int_0^L\frac{q_{\rm rad}(x)-q_0(x)}{(1+q_t(x)/\lambda(t))^{1/2}}\,\mathrm{d}x} {\int_0^L\frac{q_t(x)}{(1+q_t(x)/\lambda(t))^{1/2}}\,\mathrm{d}x}.

We here also assume that both WKB components are present, so that c1(t)c2(t)≠0c_1(t)c_2(t)\ne0 along the branch under consideration. Throughout, the square root branch is chosen continuously along the eigenvalue branch λ(t)\lambda(t), with the initial branch fixed at λ(0)\lambda(0). Now with

H(t)=∫0L(1+qt(x)λ(t))1/2 dx,H(t)=\int_0^L\left(1+\frac{q_t(x)}{\lambda(t)}\right)^{1/2}\,\mathrm{d}x,

we have, to leading order as k→∞k\to\infty,

dHdt(t)=12λ(t)∫0Lqrad(x)−q0(x)(1+qt(x)/λ(t))1/2 dx−λ′(t)2λ(t)2∫0Lqt(x)(1+qt(x)/λ(t))1/2 dx=0.\frac{\mathrm{d}H}{\mathrm{d}t}(t)=\frac{1}{2\lambda(t)}\int_0^L\frac{q_{\rm rad}(x)-q_0(x)}{(1+q_t(x)/\lambda(t))^{1/2}}\,\mathrm{d}x-\frac{\lambda'(t)}{2\lambda(t)^2}\int_0^L\frac{q_t(x)}{(1+q_t(x)/\lambda(t))^{1/2}}\,\mathrm{d}x =0.

so specifically

∫0L(1+qrad(x)λ(1))1/2 dx−L(1+∥q∥∞λ(0))1/2=H(1)−H(0)=o(1),k→∞,(9)\int_0^L\left(1+\frac{q_{\rm rad}(x)}{\lambda(1)}\right)^{1/2}\,\mathrm{d}x-L\left(1+\frac{\lVert q\rVert_\infty}{\lambda(0)}\right)^{1/2}=H(1)-H(0)=o(1),\quad k\to\infty, \tag*{(9)}

which can be solved for λ(1)\lambda(1) using a suitable zero-finding algorithm.

Case d=2d=2

Using the polar coordinates (r,θ)(r,\theta), separate the variables in (8) to get

ϕt(r,θ)=∑m=0∞r−1/2vm,t(r)(am,tcos⁡mθ+bm,tsin⁡mθ),(10)\phi_t(r,\theta)=\sum_{m=0}^{\infty}r^{-1/2}v_{m,t}(r)(a_{m,t}\cos m\theta+b_{m,t}\sin m\theta), \tag*{(10)}

where

vm,t′′(r)+k2[1+qt(r)λ(t)−m2−1/4k2r2]vm,t(r)=0,0<r<R,m∈N0,v_{m,t}''(r)+k^2\left[1+\frac{q_t(r)}{\lambda(t)}-\frac{m^2-1/4}{k^2r^2}\right]v_{m,t}(r)=0,\qquad0<r<R,\quad m\in\mathbb{N}_0,

with the regularity condition at the origin given by

r−1/2vm,t(r)=O(rm),r↘0,r^{-1/2}v_{m,t}(r)=O(r^m),\qquad r\searrow0,

and the outgoing condition for r→∞r \to\infty, as well as the continuity of vm,tv_{m,t} and vm,t′v'_{m,t} at r=Rr = R, implying

vm,t′(R)=(12R+k(Hm(1))′(kR)Hm(1)(kR))vm,t(R),m∈N0.v'_{m,t}(R) = \left(\frac{1}{2R} + k\frac{\left(H_m^{(1)}\right)'(kR)}{H_m^{(1)}(kR)}\right)v_{m,t}(R), \qquad m \in\mathbb{N}_0.

Here Hm(1)H_m^{(1)} is the Hankel function of the first kind and order mm. As long as we do not encounter exceptional points, which we in the following assume is the case, we can describe the evolution of λ(t)\lambda(t) using the spectral propagation formula (7) with any of the eigenvectors φm,t(r,θ)=r−1/2vm,t(r)(amcos⁡mθ+bmsin⁡mθ)\varphi_{m,t}(r,\theta) = r^{-1/2}v_{m,t}(r)(a_m \cos m\theta+ b_m \sin m\theta) contributing nontrivially to (10). Since we wish to use (7), we also assume that, for the chosen index mm,

∫Dqt(r)φm,t(r,θ)2r dr dθ≠0.\int_D q_t(r)\varphi_{m,t}(r,\theta)^2r\,dr\,d\theta\ne0.

Thus, with

pm,t(r;z)=(1+qt(r)z−m2−1/4k2r2)1/2p_{m,t}(r;z) = \left(1+\frac{q_t(r)}{z}-\frac{m^2-1/4}{k^2r^2}\right)^{1/2}

and

Sm,t(r)=∫r∗rpm,t(ϱ;λ(t)) dϱ,S_{m,t}(r) = \int_{r_*}^{r}p_{m,t}(\varrho;\lambda(t))\,d\varrho,

for an appropriate positive r∗r_*, the WKB approximation is to leading order given by

vm,t(r)≈pm,t(r;λ(t))−1/2(cm(t)eikSm,t(r)+dm(t)e−ikSm,t(r)).v_{m,t}(r) \approx p_{m,t}(r;\lambda(t))^{-1/2}\left(c_m(t)e^{ikS_{m,t}(r)}+d_m(t)e^{-ikS_{m,t}(r)}\right).

Substitution into the spectral evolution equation (2.3), followed by the removal of the oscillatory terms as in the one-dimensional case, and the cancellation of the cross terms due to angular orthogonality, gives

λ′(t)λ(t)=∫0Rqrad(r)−q0pm,t(r;λ(t)) dr∫0Rqt(r)pm,t(r;λ(t)) dr.\frac{\lambda'(t)}{\lambda(t)} = \frac{\int_0^R \frac{q_{\mathrm{rad}}(r)-q_0}{p_{m,t}(r;\lambda(t))}\,dr} {\int_0^R \frac{q_t(r)}{p_{m,t}(r;\lambda(t))}\,dr}.

Define

Hm(t)=∫0R(pm,t(r;λ(t))−pm,0(r;λ(0))) dr.H_m(t) = \int_0^R \left(p_{m,t}(r;\lambda(t))-p_{m,0}(r;\lambda(0))\right)\,dr.

Then, to leading order as k→∞k \to\infty,

dHmdt(t)=12λ(t)∫0Rqrad(r)−q0pm,t(r;λ(t)) dr−λ′(t)2λ(t)2∫0Rqt(r)pm,t(r;λ(t)) dr=0,\frac{dH_m}{dt}(t) = \frac{1}{2\lambda(t)}\int_0^R \frac{q_{\mathrm{rad}}(r)-q_0}{p_{m,t}(r;\lambda(t))}\,dr-\frac{\lambda'(t)}{2\lambda(t)^2}\int_0^R \frac{q_t(r)}{p_{m,t}(r;\lambda(t))}\,dr=0,

and therefore

∫0R(pm,1(r;λ(1))−pm,0(r;λ(0))) dr=Hm(1)=o(1),k→∞.(11)\int_0^R \left(p_{m,1}(r;\lambda(1))-p_{m,0}(r;\lambda(0))\right)\,dr=H_m(1)=o(1), \qquad k \to\infty. \tag*{(11)}

This equation can be solved numerically for λ(1)\lambda(1), using a zero finding algorithm and the precomputed eigenvalue λ(0)\lambda(0) of k2Vq0(k)k^2V_{q_0}(k).

Case d=3d=3

Here we have a development and argumentation analogous to the case d=2d=2: with (r,θ,ϕ)(r,\theta,\phi) the spherical coordinates, and assuming no exceptional points are encountered, we can track λ(t)\lambda(t) using (7) with any appropriate eigenvector

φℓ,m,t(r,θ,ϕ)=r−1vℓ,t(r)Yℓm(θ,ϕ),ℓ∈N0, m∈{−ℓ,…,ℓ},\varphi_{\ell,m,t}(r,\theta,\phi)=r^{-1}v_{\ell,t}(r)Y_{\ell}^{m}(\theta,\phi),\qquad\ell\in\mathbb{N}_0,\ m\in\{-\ell,\ldots,\ell\},

where

vℓ,t′′(r)+(k2(1+qt(r)/λ(t))−ℓ(ℓ+1)/r2)vℓ,t(r)=0,0<r<R,v_{\ell,t}^{\prime\prime}(r)+\left(k^2(1+q_t(r)/\lambda(t))-\ell(\ell+1)/r^2\right)v_{\ell,t}(r)=0,\qquad0<r<R,

and vℓ,t(r)=O(rℓ+1)v_{\ell,t}(r)=O(r^{\ell+1}) for r↘0r\searrow0, as well as where

vℓ,t′(R)=(1R+k(hℓ(1))′(kR)hℓ(1)(kR))vℓ,t(R),v_{\ell,t}^{\prime}(R)=\left(\frac{1}{R}+k\frac{\left(h_{\ell}^{(1)}\right)^\prime(kR)}{h_{\ell}^{(1)}(kR)}\right)v_{\ell,t}(R),

and

∫Dqt(r)φm,ℓ,t(r,θ,ϕ)2r2sin⁡θ dr dθ dϕ≠0.\int_D q_t(r)\varphi_{m,\ell,t}(r,\theta,\phi)^2r^2\sin\theta\,dr\,d\theta\,d\phi\ne0.

Here YℓmY_{\ell}^{m} is a real spherical harmonic, and hℓ(1)h_{\ell}^{(1)} is the spherical Hankel function of order ℓ\ell and of the first kind. The WKB approximation is then, to leading order,

vℓ,t(r)=pℓ,t(r;λ(t))−1/2(cℓ(t)eikSt,ℓ(r)+dℓ(t)e−ikSt,ℓ(r)),v_{\ell,t}(r)=p_{\ell,t}(r;\lambda(t))^{-1/2}\left(c_{\ell}(t)e^{ikS_{t,\ell}(r)}+d_{\ell}(t)e^{-ikS_{t,\ell}(r)}\right),

with

pℓ,t(r;z)=(1+qt(r)z−ℓ(ℓ+1)k2r2)1/2,p_{\ell,t}(r;z)=\left(1+\frac{q_t(r)}{z}-\frac{\ell(\ell+1)}{k^2r^2}\right)^{1/2},

and

St,ℓ(r)=∫r∗rpℓ,t(ϱ;λ(t)) dϱ,S_{t,\ell}(r)=\int_{r_*}^{r}p_{\ell,t}(\varrho;\lambda(t))\,d\varrho,

and this leads to

λ′(t)λ(t)=∫0Rqrad(r)−q0pℓ,t(r;λ(t)) dr∫0Rqt(r)pℓ,t(r;λ(t)) dr.(12)\frac{\lambda^\prime(t)}{\lambda(t)} = \frac{\int_0^R\frac{q_{\mathrm{rad}}(r)-q_0}{p_{\ell,t}(r;\lambda(t))}\,dr} {\int_0^R\frac{q_t(r)}{p_{\ell,t}(r;\lambda(t))}\,dr}. \tag*{(12)}

Similar to § 2.1.2, define

Hℓ(t)=∫0R(pℓ,t(r;λ(t))−pℓ,0(r;λ(0))) dr,H_\ell(t)=\int_0^R\left(p_{\ell,t}(r;\lambda(t))-p_{\ell,0}(r;\lambda(0))\right)\,dr,

and note that, to leading order as k→∞k\to\infty,

dHℓdt(t)=12λ(t)∫0Rqrad(r)−q0pℓ,t(r;λ(t)) dr−λ′(t)2λ(t)2∫0Rqt(r)pℓ,t(r;λ(t)) dr=0,\frac{dH_\ell}{dt}(t)=\frac{1}{2\lambda(t)}\int_0^R\frac{q_{\mathrm{rad}}(r)-q_0}{p_{\ell,t}(r;\lambda(t))}\,dr-\frac{\lambda^\prime(t)}{2\lambda(t)^2}\int_0^R\frac{q_t(r)}{p_{\ell,t}(r;\lambda(t))}\,dr=0,

so specifically

∫0R(pℓ,1(r;λ(1))−pℓ,0(r;λ(0))) dr=Hℓ(1)=o(1),k→∞,(13)\int_0^R\left(p_{\ell,1}(r;\lambda(1))-p_{\ell,0}(r;\lambda(0))\right)\,dr=H_\ell(1)=o(1),\qquad k\to\infty, \tag*{(13)}

which can be solved for λ(1)\lambda(1) numerically using a zero-finding algorithm and the precomputed eigenvalue λ(0)\lambda(0) of k2Vq0(k)k^2V_{q_0}(k).

Spectral correction

It remains to describe the first-order correction of the computed spectrum for k2Vqrad(k)k^{2}V_{q_{\mathrm{rad}}}(k) so that it estimates the spectrum of k2Vq(k)k^{2}V_q(k). Recall that q(x)=qrad(∣x∣)+ηQ(x)q(x)=q_{\mathrm{rad}}(|x|)+\eta Q(x) with ∥Q∥∞=1\lVert Q\rVert_{\infty}=1 and ∣η∣≪1|\eta|\ll1, and now let k2Vqrad(k)φ=λφk^{2}V_{q_{\mathrm{rad}}}(k)\varphi=\lambda\varphi and k2Vq(k)φη=ληφηk^{2}V_q(k)\varphi_\eta=\lambda_\eta\varphi_\eta, with

λη=λ+ημ+O(η2),\lambda_\eta=\lambda+\eta\mu+O(\eta^{2}),
φη=φ+ηψ+O(η2).\varphi_\eta=\varphi+\eta\psi+O(\eta^{2}).

Then Vq(k)=Vqrad(k)+ηVQ(k)V_q(k)=V_{q_{\mathrm{rad}}}(k)+\eta V_Q(k), and, to first order in η\eta,

(k2Vqrad(k)−λI)ψ=(μI−k2VQ(k))φ.(14)\left(k^{2}V_{q_{\mathrm{rad}}}(k)-\lambda I\right)\psi=\left(\mu I-k^{2}V_Q(k)\right)\varphi. \tag*{(14)}

Using again the pairing ⟨u,v⟩=∫Du(x)v(x) dx\langle u,v\rangle=\int_D u(x)v(x)\,dx and the fact that the eigenpairs of (k2Vqrad(k))T\left(k^{2}V_{q_{\mathrm{rad}}}(k)\right)^{T} are (λ,qradφ)(\lambda,q_{\mathrm{rad}}\varphi), we pair both sides of (14) with qradφq_{\mathrm{rad}}\varphi and get, to first order in η\eta, that

μ∫Dqrad(∣x∣)φ(x)2 dx=k2∫Dqrad(∣x∣)φ(x)∫DΦk(d)(x−y)Q(y)φ(y) dy dx=k2∫DQ(y)φ(y)∫DΦk(d)(x−y)qrad(∣x∣)φ(x) dx dy=∫DQ(y)φ(y)k2Vqrad(k)φ(y) dy=λ∫DQ(y)φ(y)2 dy.\begin{aligned} \mu\int_D q_{\mathrm{rad}}(|x|)\varphi(x)^2\,dx &=k^{2}\int_D q_{\mathrm{rad}}(|x|)\varphi(x)\int_D\Phi_k^{(d)}(x-y)Q(y)\varphi(y)\,dy\,dx\\ &=k^{2}\int_D Q(y)\varphi(y)\int_D\Phi_k^{(d)}(x-y)q_{\mathrm{rad}}(|x|)\varphi(x)\,dx\,dy\\ &=\int_D Q(y)\varphi(y)k^{2}V_{q_{\mathrm{rad}}}(k)\varphi(y)\,dy =\lambda\int_D Q(y)\varphi(y)^2\,dy. \end{aligned}

Thus, to first order in η\eta, we have the correction to λ\lambda given by

μ=λ∫DQ(x)φ(x)2 dx∫Dqrad(∣x∣)φ(x)2 dx.(15)\mu=\lambda\frac{\int_D Q(x)\varphi(x)^2\,dx}{\int_D q_{\mathrm{rad}}(|x|)\varphi(x)^2\,dx}. \tag*{(15)}

Recall that our proposed approach is to first solve (11) (when d=2d=2) or (13) (when $d=3) to propagate λ(t)\lambda(t) along the homotopy qt=(1−t)q0+tqradq_t=(1-t)q_0+tq_{\mathrm{rad}}, t∈[0,1]t\in[0,1], and then to correct the found λ(1)\lambda(1) using μ\mu from (15).

Estimating the optimal preconditioner parameter

Let Λ^={λ^j(1)}j=1N\widehat{\Lambda}=\{\widehat{\lambda}_j(1)\}_{j=1}^{N} be the estimated truncated discrete spectrum of k2Vq(k)k^{2}V_q(k). In applications, we will be dealing with finite matrix representations of k2Vq(k)k^{2}V_q(k), so it makes sense to assume that ∣λ∣≤δ|\lambda|\leq\delta, with known δ\delta, for all elements λ\lambda of σ(k2Vq(k))\sigma(k^{2}V_q(k)) that are omitted due to the truncation. For such elements λ\lambda, we have

∣1−γ+γλ∣≤∣1−γ∣+δ∣γ∣,|1-\gamma+\gamma\lambda|\leq|1-\gamma|+\delta|\gamma|,

so, given an admissible set Γ⊂C\Gamma\subset\mathbb{C}, we define the optimal preconditioner parameter γopt\gamma_{\mathrm{opt}} by the minimax problem

γopt∈arg⁡min⁡γ∈Γ max⁡λ^j∈Λ^{∣1+γλ^j−γ∣,∣1−γ∣+δ∣γ∣}.(16)\gamma_{\mathrm{opt}}\in\underset{\gamma\in\Gamma}{\arg\min}\ \underset{\widehat{\lambda}_j\in\widehat{\Lambda}}{\max}\left\{|1+\gamma\widehat{\lambda}_j-\gamma|,|1-\gamma|+\delta|\gamma|\right\}. \tag*{(16)}

Note that finding γopt\gamma_{\mathrm{opt}} that gives min⁡Γmax⁡Λ^{∣1+γλ^j−γ∣,∣1−γ∣+δ∣γ∣}<1\min_{\Gamma}\max_{\widehat{\Lambda}}\{|1+\gamma\widehat{\lambda}_j-\gamma|,|1-\gamma|+\delta|\gamma|\}<1 does not necessarily guarantee that the spectral radius of MγoptM_{\gamma_{\mathrm{opt}}} is less than one, since for any true eigenvalue λj\lambda_j of k2Vq(k)k^2V_q(k), approximated by λ^j∈Λ^\widehat{\lambda}_j\in\widehat{\Lambda}, we have

∣1−γ+γλj∣≤∣1−γ+γλ^j∣+∣γ∣∣λj−λ^j∣.|1-\gamma+\gamma\lambda_j|\leq|1-\gamma+\gamma\widehat{\lambda}_j|+|\gamma||\lambda_j-\widehat{\lambda}_j|.

However, in our numerical tests the solution of the minimax problem sufficed to make the modified Born series convergent. In the computations in Section 4, we take Γ\Gamma to be a rectangular box in the first quadrant,

Γ={γ=u+iv:0≤u≤γRmax⁡, 0≤v≤γImax⁡}.\Gamma=\{\gamma=u+iv:0\leq u\leq\gamma_{\mathbb{R}}^{\max},\ 0\leq v\leq\gamma_{\mathbb{I}}^{\max}\}.

For the ’exact’ preconditioner parameter used in Section 4, the optimization problem (16) is solved by Sequential Least Squares Programming (SLSQP) optimization with the estimated eigenvalues replaced by the numerically computed reference eigenvalues. Next, introducing the auxiliary variable rr, one may rewrite (16) as min⁡γ∈Γ,r≥0r\min_{\gamma\in\Gamma,r\geq0}r subject to

max⁡{∣1+γ(λ^j(1)−1)∣, ∣1−γ∣+δ∣γ∣}≤r,j=1,…,N.\max\{|1+\gamma(\widehat{\lambda}_j(1)-1)|,\ |1-\gamma|+\delta|\gamma|\}\leq r,\qquad j=1,\ldots,N.

Writing γ=u+iv\gamma=u+iv and μj=λ^j(1)−1=αj+iβj\mu_j=\widehat{\lambda}_j(1)-1=\alpha_j+i\beta_j, each constraint becomes

∥(ℜ(1+γμj)ℑ(1+γμj))∥2=∥(1+αju−βjvβju+αjv)∥2≤r,\left\|\begin{pmatrix}\Re(1+\gamma\mu_j)\\ \Im(1+\gamma\mu_j)\end{pmatrix}\right\|_2 = \left\|\begin{pmatrix}1+\alpha_ju-\beta_jv\\ \beta_ju+\alpha_jv\end{pmatrix}\right\|_2\leq r,
∥(1−uv)∥2≤s0,∥(uv)∥2≤s1,s0+δs1≤r.\left\|\begin{pmatrix}1-u\\v\end{pmatrix}\right\|_2\leq s_0,\qquad \left\|\begin{pmatrix}u\\v\end{pmatrix}\right\|_2\leq s_1,\qquad s_0+\delta s_1\leq r.

This is a convex second-order cone program in the real variables (u,v,r,s0,s1)(u,v,r,s_0,s_1). Given any candidate parameter γ\gamma, we evaluate its performance on the estimated spectrum through the contraction metric ϱ(γ):=max⁡λ^j∈Λ^{∣1+γλ^j−γ∣, ∣1−γ∣+δ∣γ∣}\varrho(\gamma):=\max_{\widehat{\lambda}_j\in\widehat{\Lambda}}\{|1+\gamma\widehat{\lambda}_j-\gamma|,\ |1-\gamma|+\delta|\gamma|\}. The optimal value with the selected parameter is ϱopt=ϱ(γopt)\varrho_{\mathrm{opt}}=\varrho(\gamma_{\mathrm{opt}}). This metric estimates the quality of the preconditioner, in that a smaller value of this objective predicts a better worst-case asymptotic convergence factor.

A second, more interpretable metric is the relative residual

r(γ,N):=∥Mγ(k)N+1V1f∥2∥V1f∥2(17)r(\gamma,N):=\frac{\|M_\gamma(k)^{N+1}V_1f\|_2}{\|V_1f\|_2} \tag*{(17)}

associated with the truncated solution

uN:=∑n=0NMγ(k)nγV1fu_N:=\sum_{n=0}^{N}M_\gamma(k)^n\gamma V_1f

of the equation (I−k2Vq(k))u=V1f(I-k^2V_q(k))u=V_1f. Indeed, since I−Mγ(k)=γ(I−k2Vq(k))I-M_\gamma(k)=\gamma(I-k^2V_q(k)), we have

γ(I−k2Vq(k))uN=γ(I−Mγ(k)N+1)V1f,\gamma(I-k^2V_q(k))u_N=\gamma(I-M_\gamma(k)^{N+1})V_1f,

so Mγ(k)N+1V1f=−((I−k2Vq(k))uN−V1f)M_\gamma(k)^{N+1}V_1f=-((I-k^2V_q(k))u_N-V_1f) is the residual associated with uNu_N. Note that r(γ,N)r(\gamma,N) is pre-computable for any γ\gamma and NN, and we can use it for a sum truncation criterion: given γ\gamma and a tolerance ε>0\varepsilon>0, the stopping index is the first NN satisfying r(γ,N)<εr(\gamma,N)<\varepsilon. Numerical experiments show that, for fixed ε\varepsilon, the choice of γ\gamma greatly affects the value of the stopping index. Moreover, we note that the spectral radius of the operator Mγ(k)=(1−γ)I+γk2Vq(k)M_{\gamma}(k) = (1-\gamma)I+\gamma k^{2}V_{q}(k) approaches 1 as γ→0\gamma\to0, so we expect that the stopping index approaches infinity as γ→0\gamma\to0 and ε\varepsilon is kept fixed. On the other hand, the spectral radius of Mγ(k)M_{\gamma}(k) being less than one requires a sufficiently small ∣γ∣|\gamma|. Thus we expect that, given a tolerance ε\varepsilon, there will in general be an optimum overrelaxation γ\gamma resulting in a smallest stopping index and hence the fastest MBS solution of the equation (I−k2Vq(k))u=V1(k)f(I-k^{2}V_{q}(k))u=V_{1}(k)f. Having fixed γ\gamma, we can now either calculate an estimate NestimateN_{\mathrm{estimate}} of the stopping index and then compute the MBS in (3) with Nestimate+1N_{\mathrm{estimate}}+1 summands, or we can test the stopping criterion r(γ,N)<εr(\gamma,N)<\varepsilon more or less frequently as the MBS is being computed.

Numerical examples

We next illustrate the proposed accelerated modified Born series approach using numerical examples in one and two dimensions. In one dimension, we consider the media q(x)=5+5sin⁡(2πx)q(x)=5+5\sin(2\pi x), q(x)=1+x2q(x)=1+x^{2}, and q(x)=1[0,1/3]+2⋅1[2/3,1]q(x)=1_{[0,1/3]}+2\cdot1_{[2/3,1]}, x∈[0,1]x\in[0,1], with the corresponding spectral radii of k2Vq(k)k^{2}V_{q}(k) being approximately 42.7, 11.5, and 9.5, respectively, and with the same source used for all three contrasts,

f(x)=k2β(∣x−0.28∣0.18)e0.3ikx,k=20π,f(x)=k^{2}\beta\left(\frac{|x-0.28|}{0.18}\right)e^{0.3ikx}, \qquad k=20\pi,

where

β(s)={exp⁡(1−11−s2),0≤s<1,0,s≥1.\beta(s)= \begin{cases} \exp\left(1-\frac{1}{1-s^{2}}\right), & 0\le s<1,\\ 0, & s\ge1. \end{cases}

Figure 1–Figure 6 demonstrate the applicability of the approach in one dimension for these cases where the spectral radius of k2Vq(k)k^{2}V_{q}(k) is significantly larger than one. Figure 7–Figure 8 support the use of the approach in two dimensions, where we have the medium

Homotopy, spectral propagation, and preconditioner selection

Figure 1. The homotopy qtq_t, spectral propagation, and selection of preconditioner γ\gamma for the case d=1d=1, q(x)=5+5sin⁡(2πx)q(x)=5+5\sin(2\pi x). The spectral radius of k2Vq(k)k^2V_q(k) is approximately 42.7. The white contour is max⁡{max⁡j∣1−γ+γλjref∣,∣1−γ∣+δ∣γ∣}=1\max\{\max_j |1-\gamma+\gamma\lambda_j^{\mathrm{ref}}|, |1-\gamma|+\delta|\gamma|\}=1, where λjref\lambda_j^{\mathrm{ref}} are the numerically computed eigenvalues of k2Vq(k)k^2V_q(k). The expression is below one inside the contour.

Plots of the considered medium function and source, numerical solutions, relative errors, and residuals

Figure 6. The considered medium function qq and source ff; comparison of MBS, direct LU, and FD solutions of (1); relative errors in the numerical solutions; relative residual in MBS solution.

The considered weakly nonradial medium and source for the example of case $d=2$, spectral propagation, and selection of preconditioner

Figure 7. The considered weakly nonradial medium qq and source ff for the example of case d=2d = 2; spectral propagation; selection of preconditioner γ\gamma. The spectral radius of k2Vq(k)k^{2}V_q(k) is approximately 4.7. The white contour is max⁡{max⁡j∣1−γ+γλjref∣,∣1−γ∣+δ∣γ∣}=1\max\{\max_j |1-\gamma+\gamma\lambda_j^{\mathrm{ref}}|, |1-\gamma|+\delta|\gamma|\}=1, where λjref\lambda_j^{\mathrm{ref}} are the numerically computed eigenvalues of k2Vq(k)k^{2}V_q(k). The expression is below one inside the contour.

Comparison plots of MBS, direct LU, and FD solutions, relative errors, and relative residual

Figure 8. Comparison of MBS, direct LU, and FD solutions of (2); relative errors; relative residual in MBS solution.

q(x)={1.1+0.1(1−∣x∣2)+0.121.35[x12−x22+0.35(x14−6x12x22+x24)],∣x∣≤1,0,∣x∣>1.q(x)= \begin{cases} 1.1+0.1(1-|x|^{2})+\dfrac{0.12}{1.35}\left[x_{1}^{2}-x_{2}^{2}+0.35\left(x_{1}^{4}-6x_{1}^{2}x_{2}^{2}+x_{2}^{4}\right)\right], & |x|\le1,\\ 0, & |x|>1. \end{cases}

and specifically η=0.12\eta=0.12 and ∥Q∥∞=1\lVert Q\rVert_{\infty}=1, as well as the source

f(x1,x2)=k2β((x1+0.36)2+(x2−0.08)20.34)e0.4ikx1,k=12,f(x_{1},x_{2})=k^{2}\beta\left(\frac{\sqrt{(x_{1}+0.36)^{2}+(x_{2}-0.08)^{2}}}{0.34}\right)e^{0.4ikx_{1}}, \qquad k=12,

supported in the disk of radius 0.34 centred at (−0.36,0.08)(-0.36,0.08). At the more demanding accuracy levels tested in Figure 9, MBS achieves a lower setup-plus-solve time than the two implemented competing methods.

Execution-time comparisons for the numerical methods

Figure 9. Execution times for the numerical methods applied to the given two-dimensional medium problem. Our accelerated MBS outperforms both direct LU and FD at sufficient accuracy.

The experiments use k=20πk=20\pi and 768 uniform cells in one dimension, and k=12k=12 on the unit disk with a 48×4848\times48 radial–angular grid in two dimensions. MBS and direct LU use the same volume-potential discretization, with piecewise constant radial elements and, in two dimensions, angular Fourier collocation. Fast matrix applications use cumulative sums and FFTs. The independent competitor uses second-order finite differences, with outgoing Robin conditions in one dimension and a perfectly matched layer in two dimensions.

Spectral propagation uses eight homotopy steps. When Newton iteration for a one-dimensional WKB action equation fails to reach the residual tolerance 2⋅10−82 \cdot10^{-8}, we restart from the initial eigenpair and follow the discretized eigenvalue problem using shifted inverse iteration with adaptive homotopy steps. The resulting endpoint replaces the WKB estimate when selecting γ\gamma. This additional computation is included in the MBS setup time. Initial eigenvalues are retained above modulus thresholds 0.01 and 0.12 in one and two dimensions, respectively; the corresponding assumed tail radii are 0.015 and 0.25. The parameter γ\gamma is selected by Sequential Least Squares Programming (SLSQP), with an additional spectral-error margin 0.015∣γ∣0.015|\gamma| in two dimensions. MBS stops at relative residual 10−810^{-8}.

The refinement study uses polar grids (24, 48), (48, 48), (96, 64), and (192, 96), and finite-difference grids with 12–72 points per shortest estimated wavelength. Errors are relative L2L^2 differences, including the polar area weight, from a common MBS reference on a 768×96768 \times96 grid with residual below 10−1010^{-10}. Additional 384×96384 \times96 and 384×80384 \times80 calculations assess reference sensitivity. Agreement with LU on the same grid measures iteration error rather than discretization accuracy.

Timings include setup and one solve, charging the full spectral setup to every MBS result. Factorization and solve times are medians of three repetitions with one BLAS/OpenMP thread.

Conclusion

We have developed an accelerated Born series method for the numerical solution of scattering problems governed by the variable-coefficient Helmholtz equation with nonnegative-valued, compactly supported, bounded, weakly non-radial media. We also provided a practical numerical procedure for selecting the overrelaxation parameter. The method is effective in the high-frequency regime, for both weak and strong scattering, and has been successfully validated against direct integral-equation and finite-difference computations.

Acknowledgements

This work was funded by Villum Foundation research grant no. 58857.

The considered medium function $q$ and source $f$; comparison of MBS, direct LU, and FD solutions of (1); relative errors in the numerical solutions; relative residual in MBS solution.

Figure 2. The considered medium function qq and source ff; comparison of MBS, direct LU, and FD solutions of (1); relative errors in the numerical solutions; relative residual in MBS solution.

The homotopy $q_t$, spectral propagation, and selection of preconditioner $\gamma$

Figure 3. The homotopy qtq_t, spectral propagation, and selection of preconditioner γ\gamma for the case d=1d = 1, q(x)=1+x2q(x) = 1 + x^2. The spectral radius of k2Vq(k)k^2V_q(k) is approximately 11.5. The white contour is max⁡{max⁡j∣1−γ+γλjref∣,∣1−γ∣+δ∣γ∣}=1\max\{\max_j |1-\gamma+\gamma\lambda_j^{\mathrm{ref}}|, |1-\gamma|+\delta|\gamma|\} = 1, where λjref\lambda_j^{\mathrm{ref}} are the numerically computed eigenvalues of k2Vq(k)k^2V_q(k). The expression is below one inside the contour.

Plots of the considered medium function and source, numerical solutions, relative errors, and residual

Figure 4. The considered medium function qq and source ff; comparison of MBS, direct LU, and FD solutions of (1); relative errors in the numerical solutions; relative residual in MBS solution.

The homotopy $q_t$, spectral propagation, and selection of preconditioner $\gamma$

Figure 5. The homotopy qtq_t, spectral propagation, and selection of preconditioner γ\gamma for the case d=1d = 1, q(x)=1[0,1/3]+2⋅1[2/3,1]q(x) = \mathbf{1}_{[0,1/3]} + 2 \cdot\mathbf{1}_{[2/3,1]}. The spectral radius of k2Vq(k)k^2 V_q(k) is approximately 9.5. The white contour is max⁡{max⁡j∣1−γ+γλjref∣,∣1−γ∣+δ∣γ∣}=1\max\{\max_j \lvert1-\gamma+\gamma\lambda_j^{\mathrm{ref}}\rvert, \lvert1-\gamma\rvert+\delta\lvert\gamma\rvert\} = 1, where λjref\lambda_j^{\mathrm{ref}} are the numerically computed eigenvalues of k2Vq(k)k^2 V_q(k). The expression is below one inside the contour.

References

  1. [1]H. Ammari and F. Triki, Splitting of resonant and scattering frequencies under shape deformation, Journal of Differential equations, 202 (2004), pp. 231–255.DOI
  2. [2]V. M. Babich, The Higher-Dimensional WKB Method or Ray Method. Its Analogues and Generalizations, Springer Berlin Heidelberg, Berlin, Heidelberg, 1999, pp. 91–131.DOI
  3. [3]D. L. Colton and R. Kress, Inverse acoustic and electromagnetic scattering theory, vol. 93, Springer, 1998.

Paper details

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

views · 0

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