[en] This paper explores a family of generalized sweeping preconditioners for Helmholtz problems with non-overlapping checkerboard partition of the computational domain. The domain decomposition procedure relies on high-order transmission conditions and cross-point treatments, which cannot scale without an efficient preconditioning technique when the number of subdomains increases. With the proposed approach, existing sweeping preconditioners, such as the symmetric Gauss-Seidel and parallel double sweep preconditioners, can be applied to checkerboard partitions with different sweeping directions (e.g. horizontal and diagonal). Several directions can be combined thanks to the flexible version of GMRES, allowing for the rapid transfer of information in the different zones of the computational domain, then accelerating the convergence of the final iterative solution procedure. Several two-dimensional finite element results are proposed to study and to compare the sweeping preconditioners, and to illustrate the performance on cases of increasing complexity.
Disciplines :
Mathematics Engineering, computing & technology: Multidisciplinary, general & others
Author, co-author :
Dai, Ruiyang ; IMMC, Université catholique de Louvain, Louvain-la-Neuve, Belgium ; Université de Liège, Institut Montefiore B28, Liège, Belgium
Modave, Axel ; POEMS, CNRS, Inria, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France
Remacle, Jean-François; IMMC, Université catholique de Louvain, Louvain-la-Neuve, Belgium
Geuzaine, Christophe ; Université de Liège - ULiège > Montefiore Institute of Electrical Engineering and Computer Science
Language :
English
Title :
Multidirectional sweeping preconditioners with non-overlapping checkerboard domain decomposition for Helmholtz problems
This work was funded in part by the Communauté Française de Belgique under contract ARC WAVES 15/19-03 (“Large Scale Simulation of Waves in Complex Media”) and by the F.R.S.-FNRS under grant PDR 26104939 (“Fast Helmholtz Solvers on GPUs”).This work was funded in part by the Communaut? Fran?aise de Belgique under contract ARC WAVES 15/19-03 (?Large Scale Simulation of Waves in Complex Media?) and by the F.R.S.-FNRS under grant PDR 26104939 (?Fast Helmholtz Solvers on GPUs?).
Astaneh, A.V., Guddati, M.N., A two-level domain decomposition method with accurate interface conditions for the Helmholtz problem. Int. J. Numer. Methods Eng. 107:1 (2016), 74–90.
Benamou, J.-D., Desprès, B., A domain decomposition method for the Helmholtz equation and related optimal control problems. J. Comput. Phys. 136:1 (1997), 68–82.
Bootland, N., Dolean, V., Jolivet, P., Tournier, P.-H., A comparison of coarse spaces for Helmholtz problems in the high frequency regime. arXiv preprint arXiv:2012.02678, 2020.
Boubendir, Y., Antoine, X., Geuzaine, C., A quasi-optimal non-overlapping domain decomposition algorithm for the Helmholtz equation. J. Comput. Phys. 231:2 (2012), 262–280.
Boubendir, Y., Midura, D., Non-overlapping domain decomposition algorithm based on modified transmission conditions for the Helmholtz equation. Comput. Math. Appl. 75:6 (2018), 1900–1911.
N. Bouziani, H. Calandra, F. Nataf, An overlapping splitting double sweep method for the Helmholtz equation, 2021.
Collino, F., Joly, P., Lecouvez, M., Exponentially convergent non overlapping domain decomposition methods for the Helmholtz equation. ESAIM: M2AN 54:3 (2020), 775–810.
Conen, L., Dolean, V., Krause, R., Nataf, F., A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator. J. Comput. Appl. Math. 271 (2014), 83–99.
Dai, R., Generalized sweeping preconditioners for domain decomposition methods applied to Helmholtz problems. PhD thesis, 2021, Université de Liège and Université catholique de Louvain, Belgique.
de La Bourdonnaye, A., Farhat, C., Macedo, A., Magoules, F., Roux, F.-X., et al. A non-overlapping domain decomposition method for the exterior Helmholtz problem. Contemp. Math. 218 (1998), 42–66.
Després, B., Domain decomposition method and the Helmholtz problem. Cohen, G., Halpern, L., Joly, P., (eds.) Proceedings of the First International Conference on Mathematical and Numerical Aspects of Wave Propagation Phenomena, Strasbourg, France, 1991, SIAM, 44–52.
Després, B., Méthodes de décomposition de domaine pour les problèmes de propagation d'ondes en régime Harmonique. Le théorème de Borg pour l'équation de Hill vectorielle. PhD thesis, 1991, Paris VI University.
Engquist, B., Majda, A., Absorbing boundary conditions for numerical simulation of waves. Proc. Natl. Acad. Sci. 74:5 (1977), 1765–1766.
Engquist, B., Ying, L., Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers. Multiscale Model. Simul. 9:2 (2011), 686–710.
Ernst, O.G., Gander, M.J., Why it is difficult to solve Helmholtz problems with classical iterative methods. Numerical Analysis of Multiscale Problems, 2012, Springer, 325–363.
Farhat, C., Avery, P., Tezaur, R., Li, J., FETI-DPH: a dual-primal domain decomposition method for acoustic scattering. J. Comput. Acoust. 13:03 (2005), 499–524.
Farhat, C., Chen, P.-S., Risler, F., Roux, F.-X., A unified framework for accelerating the convergence of iterative substructuring methods with Lagrange multipliers. Int. J. Numer. Methods Eng. 42:2 (1998), 257–288.
Gander, M., Magoules, F., Nataf, F., Optimized Schwarz methods without overlap for the Helmholtz equation. SIAM J. Sci. Comput. 24:1 (2002), 38–60.
Gander, M.J., Zhang, H., A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods. SIAM Rev. 61:1 (2019), 3–76.
Geuzaine, C., Remacle, J.-F., Gmsh: a 3-D finite element mesh generator with built-in pre- and post-processing facilities. Int. J. Numer. Methods Eng. 79:11 (2009), 1309–1331.
Hagstrom, T., Tewarson, R.P., Jazcilevich, A., Numerical experiments on a domain decomposition algorithm for nonlinear elliptic boundary value problems. Appl. Math. Lett. 1:3 (1988), 299–302.
Ihlenburg, F., Babuska, I., Finite element solution of the Helmholtz equation with high wave number part ii: the h-p version of the fem. SIAM J. Numer. Anal. 34:1 (1997), 315–358.
Kechroud, R., Antoine, X., Soulaimani, A., Numerical accuracy of a Padé-type non-reflecting boundary condition for the finite element solution of acoustic scattering problems at high-frequency. Int. J. Numer. Methods Eng. 64:10 (2005), 1275–1302.
Kim, S., Zhang, H., Optimized Schwarz method with complete radiation transmission conditions for the Helmholtz equation in waveguides. SIAM J. Numer. Anal. 53:3 (2015), 1537–1558.
Lahaye, D., Tang, J., Vuik, K., Modern Solvers for Helmholtz Problems. 2017, Springer.
Lecouvez, M., Stupfel, B., Joly, P., Collino, F., Quasi-local transmission conditions for non-overlapping domain decomposition methods for the Helmholtz equation. C. R. Phys. 15:5 (2014), 403–414.
Leng, W., Ju, L., A diagonal sweeping domain decomposition method with source transfer for the Helmholtz equation. preprint arXiv:2002.05327, 2020.
Lindman, E.L., “Free-space” boundary conditions for the time-dependent wave equation. J. Comput. Phys. 18:1 (1975), 66–78.
Lions, P.-L., On the Schwarz alternating method III: a variant for nonoverlapping subdomains. Third International Symposium on Domain Decomposition Methods for Partial Differential Equations, 1990.
Marsic, N., Gersem, H.D., Convergence of optimized non-overlapping Schwarz method for Helmholtz problems in closed domains. preprint arXiv:2001.01502, 2020.
Milinazzo, F.A., Zala, C.A., Brooke, G.H., Rational square-root approximations for parabolic equation algorithms. J. Acoust. Soc. Am. 101:2 (1997), 760–766.
Modave, A., Geuzaine, C., Antoine, X., Corner treatments for high-order local absorbing boundary conditions in high-frequency acoustic scattering. J. Comput. Phys., 401, 2020, 109029.
Modave, A., Royer, A., Antoine, X., Geuzaine, C., A non-overlapping domain decomposition method with high-order transmission conditions and cross-point treatment for Helmholtz problems. Comput. Methods Appl. Mech. Eng., 368, 2020, 113162.
Nataf, F., On the use of open boundary conditions in block Gauss-Seidel methods for the convection-diffusion equations. Technical report, 1993, CMAP (Ecole Polytechnique).
Nataf, F., Nier, F., Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains. Numer. Math. 75:3 (1997), 357–377.
Nataf, F., Rogier, F., de Sturler, E., Optimal interface conditions for domain decomposition methods. Technical report, 1994, CMAP (Ecole Polytechnique).
Nicolopoulos, A., Formulations variationnelles d'équations de Maxwell résonantes et problèmes aux coins en propagation d'ondes. PhD thesis, 2019, Sorbonne Université.
Piacentini, A., Rosa, N., An improved domain decomposition method for the 3D Helmholtz equation. Comput. Methods Appl. Mech. Eng. 162:1–4 (1998), 113–124.
Royer, A., Geuzaine, C., Béchet, E., Modave, A., A non-overlapping domain decomposition method with perfectly matched layer transmission conditions for the Helmholtz equation. preprint https://hal.archives-ouvertes.fr/hal-03416187, Nov. 2021.
Saad, Y., A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput. 14:2 (1993), 461–469.
Saad, Y., Iterative Methods for Sparse Linear Systems. 2003, SIAM.
Schädle, A., Zschiedrich, L., Additive Schwarz method for scattering problems using the PML method at interfaces. Domain Decomposition Methods in Science and Engineering XVI, 2007, Springer, 205–212.
Stolk, C.C., A rapidly converging domain decomposition method for the Helmholtz equation. J. Comput. Phys. 241 (2013), 240–252.
Stolk, C.C., An improved sweeping domain decomposition preconditioner for the Helmholtz equation. Adv. Comput. Math. 43:1 (2017), 45–76.
Stupfel, B., Improved transmission conditions for a one-dimensional domain decomposition method applied to the solution of the Helmholtz equation. J. Comput. Phys. 229:3 (2010), 851–874.
Taus, M., Zepeda-Núñez, L., Hewett, R.J., Demanet, L., L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation. J. Comput. Phys., 420, 2020, 109706.
Vion, A., Geuzaine, C., Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem. J. Comput. Phys. 266 (2014), 171–190.
Vion, A., Geuzaine, C., Improved sweeping preconditioners for domain decomposition algorithms applied to time-harmonic Helmholtz and Maxwell problems. ESAIM Proc. Surv. 61 (2018), 93–111.
Zepeda-Núñez, L., Demanet, L., The method of polarized traces for the 2D Helmholtz equation. J. Comput. Phys. 308 (2016), 347–388.
