Massively parallel Schwarz methods for the high frequency Helmholtz equation Yan Xie \orcidID 0009-0004-2861-3383, Shihua Gong \orcidID 0000-0003-3650-2283, Ivan G. Graham \orcidID 0000-0002-5730-676X, Euan A. Spence \orcidID 0000-0003-1236-4592, Chen-Song Zhang \orcidID 0000-0002-2213-0899 Abstract We investigate the parallel one-level overlapping Schwarz method for solving finite element discretization of high-frequency Helmholtz equations. The resulting linear systems are large, indefinite, ill-conditioned, and complex-valued. We present a practical variant of the restricted additive Schwarz method with Perfectly Matched Layer transmission conditions (RAS-PML), which was originally analyzed in a theoretical setting in arXiv:2404.02156 , with some numerical experiments given in arXiv:2408.16580 . In our algorithm, the width of the overlap and the additional PML layer on each subdomain is allowed to decrease with 𝒪 ⁡ ( k − 1 ​ log ⁡ ( k ) ) \mathcal{O}(k^{-1}\log(k)) , as the frequency k → ∞ k\rightarrow\infty , and this is observed to ensure good convergence while avoiding excessive communication. In experiments, the proposed method achieves 𝒪 ⁡ ( k d ) \mathcal{O}(k^{d}) parallel scalability under Cartesian domain decomposition and exhibits 𝒪 ⁡ ( k ) \mathcal{O}(k) iteration counts and convergence time for d d -dimensional Helmholtz problems ( d = 2 , 3 d=2,3 ) as k k increases. In this preliminary note we restrict to experiments on 2D problems with constant wave speed. Details, analysis and extensions to variable wavespeed and 3D will be given in future work. 1 The Helmholtz problem We consider the classical Helmholtz equation given by \Delta u+\frac{k^{2}}{c^{2}}u=-f\quad\text{in}\quad\mathbb{R}^{d}, (1) subject to the Sommerfeld radiation condition: \frac{\partial u}{\partial r}-\mathrm{i}ku=o\left(\frac{1}{r^{(d-1)/2}}\right),\quad r=|x|\to\infty. (2) Here k is the angular frequency, c\in C^{\infty}(\mathbb{R}^{d}) represents the (possibly variable) wave speed, and f\in L^{2}(\mathbb{R}^{d}) is the source term. We assume that both f and 1-c are compactly supported within a hyper-rectangle \Omega_{\text{int}}:=\prod_{i=1}^{d}(a^{i},b^{i}) . To keep the presentation simple, we restrict here to constant wave speed case c=1 . To formulate the problem in a bounded computational domain, we restrict ( 1 ) to the extended domain \Omega:=\prod_{i=1}^{d}(a^{i}-\kappa_{\rm g},b^{i}+\kappa_{\rm g}) , where \kappa_{\rm g} denotes the thickness of the Cartesian PML surrounding \Omega_{\text{int}} . We introduce a smooth scaling function g\in C^{\infty}(\mathbb{R}) , satisfying \begin{cases}g(x)=g^{\prime}(x)=0,&x\leq 0\\ g^{\prime}(x)>0,&x>0\\ g^{\prime\prime}(x)=0,&x\in(\kappa_{\infty},+\infty)\end{cases} The scaling function g_{i}(x) for each direction i is then given by: g_{i}(x^{i})=\begin{cases}g(x^{i}-b^{i}),&x^{i}\geq b^{i}\\ 0,&x^{i}\in(a^{i},b^{i})\\ -g(a^{i}-x^{i}),&x^{i}\leq a^{i}\end{cases} Using these, we define the PML-modified Laplacian as: \Delta_{pml}:=\sum_{i=1}^{d}\left(\gamma_{i}(x^{i})^{-1}\partial_{x^{i}}\right)^{2} where \gamma_{i}:=1+\mathrm{i}g^{\prime}_{i} . This formulation allows for the analytic continuation of the solution into complex coordinates, effectively absorbing outgoing waves. In weak formulation, the truncated Helmholtz problem with PML reads: find u\in H^{1}_{0}(\Omega) such that a(u,v):=\int_{\Omega}(D\nabla u)\cdot\nabla v-(\beta\cdot\nabla u)v-k^{2}uv=\int_{\Omega}fv,\quad\forall v\in H^{1}_{0}(\Omega). (3) where D is the diagonal matrix with entries D_{ii}=\gamma_{i}(x^{i})^{-2} , and \beta is the vector field with components \beta_{i}=\gamma_{i}^{\prime}(x^{i})/\gamma_{i}(x^{i})^{3} . 2 Restricted additive Schwarz method with PML transmission conditions The work 3 analyzed Schwarz methods (both additive and multiplicative) with perfectly matched layer transmission conditions, and provided theoretical convergence results for these when applied to the high-frequency Helmholtz equation. In this paper, we implement a practical variant of the additive method and present numerical results to demonstrate that it is scalable to \mathcal{O}(k^{d}) pocessors. Earlier work with lower levels of parallel scaling can be found in 7 ; 6 ; 2 . To keep the presentation self-contained, we summarize here the key components of the method. Cartesian covering. We cover the computational domain \Omega with N overlapping subdomains \Omega_{j,\rm int}:=\prod_{i=1}^{d}(a^{i}_{j},b^{i}_{j}),j=1,\cdots,N obtained by extending a non-overlapping Cartesian partition in each coordinate direction. The overlap width is \delta . We then extend each interior boundary \partial\Omega_{j,\rm int}\not\subset\partial\Omega by a PML layer to obtain \Omega_{j}=\prod_{i=1}^{d}(a^{i}_{j}-\kappa_{j,l}^{i},b^{i}_{j}+\kappa_{j,u}^{i}) , where \kappa_{j,l}^{i}=\begin{cases}0,&a^{i}_{j}=a^{i}-\kappa_{\rm g}\\ \kappa,&a^{i}_{j}>a^{i}-\kappa_{\rm g}\end{cases},\quad\kappa_{j,u}^{i}=\begin{cases}0,&b^{i}_{j}=b^{i}+\kappa_{\rm g}\\ \kappa,&b^{i}_{j}0 and integer s\geq 1 , there exist constants \mathcal{N}\in\mathbb{N} and k_{0}>0 (both independent of f ) such that \displaystyle\|u-u^{{(\mathcal{N})}}\|_{H_{k}^{s}(\Omega)}\leq k^{-M}\|u-u^{(0)}\|_{H_{k}^{1}(\Omega)},\ \text{for}\ k>k_{0}. (8) Here the weighted Sobolev norm is defined as ||v||^{2}_{H^{s}_{k}(\Omega)}:=\sum_{|\alpha|\leq s}||(k^{-1}\partial)^{\alpha}v||^{2}_{L^{2}(\Omega)}. In particular, ( 8 ) implies that the fixed-point iterations converge super-algebraically fast in the number of iterations for sufficiently-large k , and that the rate of convergence improves as k increases. These theoretical results apply on arbitrary overlap \delta and PML width \kappa , but these have to remain fixed as k increases. Mesh refinement and number of subdomains. To resolve the oscillatory solutions of ( 1 ), the mesh size must decrease at least as fast as h=\mathcal{O}(k^{-1}) as k\rightarrow\infty , leading to a finite element system with at least \mathcal{O}(k^{d}) degrees of freedom (DoFs). To achieve efficient parallelization, we partition the domain first into \mathcal{O}(k) non-overlapping subdomains along each coordinate direction, so that the number of DoFs within each remains approximately constant as k grows. Then we add the overlap and PML layers of thickness \delta,\kappa as described above. The case of meshes refined to avoid the pollution effect will also be discussed in future work. Although the theory in 3 assumes that \delta,\kappa should be fixed with respect to k , the results here show that these parameters can be chosen to decrease quickly as k increases, leading to a scalable algorithm with no loss of convergence rate. (Preliminary experiments were given in 4 .) 3 Practical improvements We propose several practical improvements to Algorithm 1 which will be illustrated by the numerical experiments below. These include: (i) Reducing communication by exploiting the sparsity of the residual term. It can be shown that the right-hand side of ( 5 ) is nonzero only in overlapping regions, and thus the communication of the local residuals can be restricted to these regions. (ii) Combining PML and impedance boundary conditions for improved robustness. The fact that the local corrections ( 5 ) are computed in V_{h,j}\subset H^{1}_{0}(\Omega_{j}) implies that a Dirichlet condition is applied at the boundary \partial\Omega_{j} . (This is a common set-up when PML is used.) However it is simple to apply instead the impedance boundary condition {\partial_{\nu_{j}}u}-\mathrm{i}ku=0\quad\text{on}\quad\partial\Omega_{j}, (9) (as a natural boundary condition on subdomains), where \partial_{\nu_{j}} denotes is the outward normal derivative on \partial\Omega_{j} , i.e. we use a hybrid of the PML with impedance boundary conditions. The local sesquilinear forms a_{j} then incorporate ( 9 ) as a natural boundary condition. This improves robustness when the PML is thin (see Table 1 ). This hybrid treatment, also used for Maxwell’s equations 1 , yields smaller errors than PML with Dirichlet boundary condition. (iii) Scaling of width of overlap and PML layers as k increases. To balance communication and convergence, we have found that it is advantageous to let the number of grid points in the overlap and PML layers grow logarithmically with k . Since the mesh diameter in these experiments is of the order of a wavelength \lambda=2\pi/k , we choose overlap \delta and PML width \kappa according to the formulae \delta=C_{\delta}\,\ell(k)\,\frac{2\pi}{k}\quad\text{and}\quad\kappa=C_{\kappa}\,\ell(k)\,\frac{2\pi}{k}, (10) where \ell(k):=\frac{k}{k-k_{0}}\log_{2}(k/k_{0}) , for some constants k_{0} , C_{\delta} and C_{\kappa} to be chosen. 4 Numerical experiments In our numerical tests, \Omega is the unit square, and the source is the smoothed delta function: f(x)=\frac{16k^{2}}{\pi^{3}}\exp\left(-\frac{16k^{2}(x-x_{c})^{2}}{\pi^{2}}\right), with the source point x_{c}=(0.5,0.5) , the global PML width is \kappa_{g}=3\frac{2\pi}{k} (i.e., 3 wavelengths) and the PML coordinate scaling function is taken to be g(x)=10kx^{3} . For this experiment the problem ( 1 ) is discretized on a uniform square mesh with 12 grid points per wavelength using bilinear elements. The domain decomposition consists of N uniform overlapping square subdomains and the PoU functions are taken to be the tensor products of the 1D PoU functions which vary linearly across the overlap regions in each direction. In the tables, ovlp and pml denote the number of grid points in the overlapping and PML regions respectively. For the formula ( 10 ) of \delta and \kappa , we use \ell(k) with k_{0}=150 . In all cases, the number of processors is equal to the total number of subdomains N=\mathcal{O}(k^{2}) , chosen so that each non-overlapping subdomain has a bounded number of degrees of freedom as k\rightarrow\infty . Iterations are terminated when the relative residual is below rtol=1E-10 or the number of iterations exceeds 500. 4.1 Different types of boundary conditions We first compare the performance of three subdomain boundary condition strategies: RAS-PML-Drch means that a PML is combined with a subdomain Dirichlet boundary condition, as implied by ( 5 ). RAS-PML-Imp means that a PML is combined with a subdomain impedance boundary condition, as described in §3(ii), while RAS-Imp means that the PML is discarded and the impedance boundary condition ( 9 ) is imposed directly on subdomain boundaries. A comparison of these three strategies is given in Table 1 . RAS-PML-Imp exhibits superior performance over RAS-PML-Drch, particularly at high frequencies, while RAS-Imp fails to converge at all for high k . To further enhance convergence, we use the Algorithm 1 as a preconditioner for the Krylov method GMRES. The results in Table 2 show a significant improvement over Table 1 , with RAS-PML-Imp remaining the most effective. However, since GMRES entails higher communication costs and offers little advantage when convergence is already satisfactory, we only employ the simple Richardson iteration ( 5 ), ( 6 ) in the following experiments. From now on, we refer to RAS-PML-Imp simply as RAS-PML for brevity. Table 1 : The performance of RAS-PML-Imp, RAS-PML-Drch and RAS-Imp. \kappa , \delta in ( 10 ) with C_{\kappa}=3/8,\ C_{\delta}=1/6 RAS-PML-Imp RAS-PML-Drch RAS-Imp k grid N pml ovlp iter relres iter relres iter relres 300 600^{2} 4 8 4 12 1.88E-11 13 2.29E-11 30 6.44E-11 600 1200^{2} 16 11 5 17 9.15E-11 18 7.22E-11 43 7.13E-11 1200 2400^{2} 64 15 6 34 7.26E-11 35 8.83E-11 500 0.016 2400 4800^{2} 256 18 8 77 8.98E-11 94 8.91E-11 \times -diverged- 4800 9600^{2} 1024 22 10 196 9.12E-11 500 1.17E-10 \times -diverged- 9600 19200^{2} 4096 26 12 500 4.43E-08 \times -diverged- \times -diverged- Table 2 : Use GMRES to improve the performance of RAS-PML-Imp, RAS-PML-Drch and RAS-Imp with slightly thin PML thickness. \kappa , \delta in ( 10 ) with C_{\kappa}=3/8,\ C_{\delta}=1/6 RAS-PML-Imp RAS-PML-Drch RAS-Imp k grid N pml ovlp iter relres iter relres iter relres 300 600^{2} 4 8 4 11 7.86E-11 12 8.84E-11 29 6.71E-11 600 1200^{2} 16 11 5 19 6.90E-11 19 6.28E-11 41 8.34E-11 1200 2400^{2} 64 15 6 48 9.30E-11 49 9.31E-11 95 8.20E-11 2400 4800^{2} 256 18 8 88 8.50E-11 91 5.30E-11 310 9.24E-11 4800 9600^{2} 1024 22 10 154 6.93E-11 173 9.62E-11 500 4.49E-10 9600 19200^{2} 4096 26 12 294 8.90E-11 389 9.92E-11 500 9.24E-06 4.2 Choice of PML and overlapping width We next compare the convergence behavior of RAS-PML under different choices of PML and overlap widths. Table 3 shows that with \kappa chosen as a fixed multiple of wavelength, RAS-PML eventually diverges, independently of whether \delta contains a fixed or logarithmically growing number of grid-points. In contrast, if \kappa is chosen as in ( 10 ) then convergence is obtained both for \delta chosen as a multiple of wavelength or growing more quickly as in ( 10 ), with the latter producing the best iteration counts, in fact with close to linear growth as frequency increases. Then Table 4 shows that this strategy results in a total runtime that increases linearly with respect to k . Table 3 : The performance of RAS-PML with different PML and overlapping width. \kappa=2\frac{2\pi}{k} \kappa in ( 10 ) with C_{\kappa}=1/2 k grid N \delta=\frac{2}{3}\frac{2\pi}{k} \delta in ( 10 ) with C_{\delta}=1/6 \delta=\frac{1}{3}\frac{2\pi}{k} \delta in ( 10 ) with C_{\delta}=1/6 pml ovlp iter pml ovlp iter pml ovlp iter ratio pml ovlp iter ratio 300 600^{2} 4 25 8 6 25 4 7 12 4 7 - 12 4 7 - 600 1200^{2} 16 25 8 13 25 5 14 16 4 14 2.00 16 5 14 2.00 1200 2400^{2} 64 25 8 26 25 6 31 21 4 31 2.21 21 6 31 2.21 2400 4800^{2} 256 25 8 61 25 8 61 26 4 72 2.32 26 8 60 1.94 4800 9600^{2} 1024 25 8 140 25 10 134 32 4 149 2.07 32 10 119 1.98 9600 19200^{2} 4096 25 8 \times 25 12 >500 38 4 298 2.00 38 12 224 1.88 Table 4 : Time table where the total runtime increase with \mathcal{O}(k) . \kappa , \delta in ( 10 ) with C_{\kappa}=1/2,\ C_{\delta}=1/6 rtol=1E-10 k grid N pml ovlp iter setup(s) solve(s) total time(s) total/ k 300 600^{2} 4 12 4 7 0.95 0.27 1.22 0.0041 600 1200^{2} 16 16 5 14 1.12 0.68 1.80 0.0030 1200 2400^{2} 64 21 6 31 1.40 1.87 3.27 0.0027 2400 4800^{2} 256 26 8 60 1.67 4.39 6.06 0.0025 4800 9600^{2} 1024 32 10 119 1.94 11.20 13.15 0.0027 9600 19200^{2} 4096 38 12 224 1.90 23.22 25.12 0.0026 5 Conclusion We describe several improvements of our previous work 5 ; 3 ; 4 to develop a practical parallel RAS-PML method for solving high-frequency Helmholtz equations. We apply both PMLs and impedance boundary conditions for subdomains to make the method more robust. We show by experiment that allowing the PML width to contain a logarithmically growing number of grid points can yield good convergence rates without excessive computation and communication. Under a Cartesian covering with \mathcal{O}(k^{2}) subdomains for 2D problems with \mathcal{O}(k^{2}) DoFs, numerical experiments demonstrate that both iteration counts and total runtime grow nearly linearly for the increasing frequency k . Full details, analysis and extensions to variable wavespeed and 3D are given in future work. Acknowledgments. SG was supported by the National Natural Science Foundation of China (grant number 12201535) and Shenzhen Stability Science Program 2022. ES was supported by the ERC synergy grant “PSINumScat” 101167139.