L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation. (English) Zbl 07506624
Summary: We present the first fast solver for the high-frequency Helmholtz equation that scales optimally in parallel for a single right-hand side. The L-sweeps approach achieves this scalability by departing from the usual propagation pattern, in which information flows in a \(180^\circ\) degree cone from interfaces in a layered decomposition. Instead, with L-sweeps, information propagates in \(90^\circ\) cones induced by a Cartesian domain decomposition (CDD). We extend the notion of accurate transmission conditions to CDDs and introduce a new sweeping strategy to efficiently track the wave fronts as they propagate through the CDD. The new approach decouples the subdomains at each wave front, so that they can be processed in parallel, resulting in better parallel scalability than previously demonstrated in the literature. The method has an overall \(\mathcal{O}((N/p)\log\omega)\) empirical run-time for \(N = n^d\) total degrees-of-freedom in a \(d\)-dimensional problem, frequency \(\omega\), and \(p = \mathcal{O}(n)\) processors. We introduce the algorithm and provide a complexity analysis for our parallel implementation of the solver. We corroborate all claims in several two- and three-dimensional numerical examples involving constant, smooth, and discontinuous wave speeds.
Keywords:
Helmholtz equation; fast high-frequency solvers; high performance computing; wave propagationReferences:
| [1] | Amestoy, P.; Brossier, R.; Buttari, A.; L’Excellent, J.-Y.; Mary, T.; Métivier, L.; Miniussi, A.; Operto, S., Fast 3D frequency-domain full-waveform inversion with a parallel block low-rank multifrontal direct solver: application to OBC data from the North Sea, Geophysics, 81, R363-R383 (2016) |
| [2] | Amestoy, P. R.; Duff, I. S.; L’Excellent, J.-Y.; Koster, J., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41 (2001) · Zbl 0992.65018 |
| [3] | Aruliah, D.; Ascher, U., Multigrid preconditioning for Krylov methods for time-harmonic Maxwell’s equations in three dimensions, SIAM J. Sci. Comput., 24, 2, 702-718 (2002) · Zbl 1016.65091 |
| [4] | 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, 74-90 (2016), nme.5164 · Zbl 1352.74319 |
| [5] | Ballard, G.; Demmel, J.; Holtz, O.; Schwartz, O., Minimizing communication in numerical linear algebra, SIAM J. Matrix Anal. Appl., 32, 3, 866-901 (2011) · Zbl 1246.68128 |
| [6] | Bebendorf, M., Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Lecture Notes in Computational Science and Engineering (LNCSE), vol. 63 (2008), Springer-Verlag · Zbl 1151.65090 |
| [7] | Bérenger, J.-P., A perfectly matched layer for the absorption of electromagnetic waves, J. Comput. Phys., 114, 2, 185-200 (1994) · Zbl 0814.65129 |
| [8] | Billette, F.; Brandsberg-Dahl, S., The 2004 BP Velocity Benchmark (2005), EAGE |
| [9] | Boerm, S.; Grasedyck, L.; Hackbusch, W., Hierarchical Matrices, Max-Planck-Institute Lecture Notes (2006) |
| [10] | Boubendir, Y., An analysis of the BEM-FEM non-overlapping domain decomposition method for a scattering problem, J. Comput. Appl. Math., 204, 2, 282-291 (2007), Special Issue: The Seventh International Conference on Mathematical and Numerical Aspects of Waves (WAVES’05) · Zbl 1117.65151 |
| [11] | Boubendir, Y.; Antoine, X.; Geuzaine, C., A quasi-optimal non-overlapping domain decomposition algorithm for the Helmholtz equation, J. Comput. Phys., 231, 2, 262-280 (2012) · Zbl 1243.65144 |
| [12] | Bramble, J.; Pasciak, J., Analysis of a finite PML approximation for the three dimensional time-harmonic Maxwell and acoustic scattering problems, Math. Comput., 76, 258, 597-614 (2007) · Zbl 1116.78019 |
| [13] | Brandt, A.; Livshits, I., Wave-ray multigrid method for standing wave equations, Electron. Trans. Numer. Anal., 6, 162-181 (1997) · Zbl 0891.65127 |
| [14] | Calandra, H.; Gratton, S.; Pinel, X.; Vasseur, X., An improved two-grid preconditioner for the solution of three-dimensional Helmholtz problems in heterogeneous media, Numer. Linear Algebra Appl., 20, 4, 663-688 (2013) · Zbl 1313.65284 |
| [15] | Chan, T. F.; Mathew, T. P., Domain decomposition algorithms, Acta Numer., 3, 61-143, 1 (1994) · Zbl 0809.65112 |
| [16] | Chen, Z.; Xiang, X., A source transfer domain decomposition method for Helmholtz equations in unbounded domain, SIAM J. Numer. Anal., 51, 4, 2331-2356 (2013) · Zbl 1285.65082 |
| [17] | Collino, F.; Ghanemi, S.; Joly, P., Domain decomposition method for harmonic wave propagation: a general presentation, Comput. Methods Appl. Mech. Eng., 184, 2-4, 171-211 (2000) · Zbl 0965.65134 |
| [18] | Davis, T. A., Algorithm 832: UMFPACK v4.3—an unsymmetric-pattern multifrontal method, ACM Trans. Math. Softw., 30, 2, 196-199 (June 2004) · Zbl 1072.65037 |
| [19] | de Hoop, M. V.; Wang, S.; Xia, J., On 3D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver, Geophys. Prospect., 59, 5, 857-873 (2011) |
| [20] | de La Bourdonnaye, A.; Farhat, C.; Macedo, A.; Magoules, F.; Roux, F.-X., A non-overlapping domain decomposition method for the exterior Helmholtz problem, Contemp. Math., 218, 42-66 (1998) · Zbl 0909.65103 |
| [21] | Demmel, J.; Grigori, L.; Gu, M.; Xiang, H., Communication avoiding rank revealing qr factorization with column pivoting (May 2013), EECS Department: EECS Department University of California Berkeley, Technical Report UCB/EECS-2013-46 |
| [22] | Demmel, J. W.; Eisenstat, S. C.; Gilbert, J. R.; Li, X. S.; Liu, J. W.H., A supernodal approach to sparse partial pivoting, SIAM J. Matrix Anal. Appl., 20, 3, 720-755 (1999) · Zbl 0931.65022 |
| [23] | Després, B., Décomposition de domaine et problème de Helmholtz, C. R. Séances Acad. Sci., Sér. 1 Math., 311, 313-316 (1990) · Zbl 0729.35035 |
| [24] | Duff, I. S.; Reid, J. K., The multifrontal solution of indefinite sparse symmetric linear, ACM Trans. Math. Softw., 9, 3, 302-325 (September 1983) · Zbl 0515.65022 |
| [25] | Engquist, B.; Ying, L., Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation, Commun. Pure Appl. Math., 64, 5, 697-735 (2011) · Zbl 1229.35037 |
| [26] | Engquist, B.; Ying, L., Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers, Multiscale Model. Simul., 9, 2, 686-710 (2011) · Zbl 1228.65234 |
| [27] | Engquist, B.; Zhao, H.-K., Absorbing boundary conditions for domain decomposition, Appl. Numer. Math., 27, 4, 341-365 (1998), Special Issue on Absorbing Boundary Conditions · Zbl 0935.65135 |
| [28] | Erlangga, Y. A.; Oosterlee, C. W.; Vuik, C., A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM J. Sci. Comput., 27, 4, 1471-1492 (2006) · Zbl 1095.65109 |
| [29] | Ernst, O. G.; Gander, M. J., Why it is difficult to solve Helmholtz problems with classical iterative methods, (Graham, Ivan G.; Hou, Thomas Y.; Lakkis, Omar; Scheichl, Robert, Numerical Analysis of Multiscale Problems. Numerical Analysis of Multiscale Problems, Lecture Notes in Computational Science and Engineering, vol. 83 (2012), Springer: Springer Berlin, Heidelberg), 325-363 · Zbl 1248.65128 |
| [30] | Fang, J.; Qian, J.; Zepeda-Núñez, L.; Zhao, H., Learning dominant wave directions for plane wave methods for high-frequency Helmholtz equations, Res. Math. Sci., 4, 1, 9 (May 2017) · Zbl 1425.35016 |
| [31] | Gander, M.; Nataf, F., AILU for Helmholtz problems: a new preconditioner based on an analytic factorization, C. R. Acad. Sci., Ser. 1 Math., 331, 3, 261-266 (2000) · Zbl 0960.65054 |
| [32] | Gander, M.; 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, 3-76 (2019) · Zbl 1417.65216 |
| [33] | Gander, M. J., Optimized Schwarz methods, SIAM J. Numer. Anal., 44, 2, 699-731 (2006) · Zbl 1117.65165 |
| [34] | Gander, M. J.; Kwok, F., Optimal interface conditions for an arbitrary decomposition into subdomains, (Huang, Yunqing; Kornhuber, Ralf; Widlund, Olof; Xu, Jinchao, Domain Decomposition Methods in Science and Engineering XIX. Domain Decomposition Methods in Science and Engineering XIX, Lecture Notes in Computational Science and Engineering, vol. 78 (2011), Springer: Springer Berlin, Heidelberg), 101-108 · Zbl 1217.65223 |
| [35] | Gander, M. J.; Magoulès, F.; Nataf, F., Optimized Schwarz methods without overlap for the Helmholtz equation, SIAM J. Sci. Comput., 24, 1, 38-60 (2002) · Zbl 1021.65061 |
| [36] | Gander, M. J.; Xu, Y., Optimized Schwarz method with two-sided transmission conditions in an unsymmetric domain decomposition, (Domain Decomposition Methods in Science and Engineering XXII (2016), Springer International Publishing: Springer International Publishing Cham), 631-639 · Zbl 1339.65234 |
| [37] | Gander, M. J.; Zhang, H., Domain decomposition methods for the Helmholtz equation: a numerical investigation, (Bank, Randolph; Holst, Michael; Widlund, Olof; Xu, Jinchao, Domain Decomposition Methods in Science and Engineering XX. Domain Decomposition Methods in Science and Engineering XX, Lecture Notes in Computational Science and Engineering, vol. 91 (2013), Springer: Springer Berlin, Heidelberg), 215-222 |
| [38] | Gander, M. J.; Zhang, H., Optimized Schwarz methods with overlap for the Helmholtz equation, (Domain Decomposition Methods in Science and Engineering XXI (2014), Springer International Publishing: Springer International Publishing Cham), 207-215 · Zbl 1382.65442 |
| [39] | Gander, M. J.; Graham, I. G.; Spence, E. A., Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: what is the largest shift for which wavenumber-independent convergence is guaranteed?, Numer. Math., 1-48 (2015) |
| [40] | George, A., Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10, 345-363 (1973) · Zbl 0259.65087 |
| [41] | Ghanemi, S., A domain decomposition method for Helmholtz scattering problems, (Ninth International Conference on Domain Decomposition Methods (1998)), 105-112 |
| [42] | Gillman, A.; Barnett, A. H.; Martinsson, P.-G., A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media, BIT Numer. Math., 55, 1, 141-170 (Mar 2015) · Zbl 1312.65201 |
| [43] | Gordon, Dan; Carp-cg, Rachel Gordon, A robust and efficient parallel solver for linear systems, applied to strongly convection dominated {PDEs}, Parallel Comput., 36, 9, 495-515 (2010) · Zbl 1195.65062 |
| [44] | Hiptmair, R.; Moiola, A.; Perugia, I., Plane wave discontinuous Galerkin methods for the 2D Helmholtz equation: analysis of the p-version, SIAM J. Numer. Anal., 49, 1, 264-284 (2011) · Zbl 1229.65215 |
| [45] | Hiptmair, R.; Moiola, A.; Perugia, I., A survey of Trefftz methods for the Helmholtz equation, (Barrenechea, G. R.; Brezzi, F.; Cangiani, A.; Georgoulis, E. H., Building Bridges: Connections and Challenges in Modern Approaches to Numerical Partial Differential Equations (2016), Springer), 237-278 |
| [46] | Hockney, R. W., A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM, 12, 1, 95-113 (January 1965) · Zbl 0139.10902 |
| [47] | Hu, Q.; Zhang, H., Substructuring preconditioners for the systems arising from plane wave discretization of Helmholtz equations, SIAM J. Sci. Comput., 38, 4, A2232-A2261 (2016) · Zbl 1342.65219 |
| [48] | S. Johnson, March 2010, Notes on perfectly matched layers (PMLs). |
| [49] | Kourounis, D.; Fuchs, A.; Schenk, O., Toward the next generation of multiperiod optimal power flow solvers, IEEE Trans. Power Syst., 33, 4, 4005-4014 (July 2018) |
| [50] | Laird, A.; Giles, M., Preconditioned iterative solution of the 2D Helmholtz equation (May 2002), Computing Lab, Oxford University, Technical Report NA 02-12 |
| [51] | Leng, W.; Ju, L., An additive overlapping domain decomposition method for the Helmholtz equation, SIAM J. Sci. Comput., 41, 2, A1252-A1277 (2019) · Zbl 1416.65501 |
| [52] | Li, X. S.; Demmel, J. W., SuperLU DIST: a scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Trans. Math. Softw., 29, 2, 110-140 (June 2003) · Zbl 1068.90591 |
| [53] | Li, Y.; Métivier, L.; Brossier, R.; Han, B.; Virieux, J., 2D and 3D frequency-domain elastic wave modeling in complex media with a parallel iterative solver, Geophysics, 80, T101-T118 (2015) |
| [54] | Lions, P.-L., On the Schwarz alternating method II, (Chan, Tony; Glowinski, Roland; Periaux, Jacques; Widlund, Olof, Domain Decomposition Methods. Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering (1989), SIAM), 47-70 · Zbl 0681.65072 |
| [55] | F. Liu, L. Ying, Recursive sweeping preconditioner for the 3D Helmholtz equation. ArXiv e-prints, 2015. |
| [56] | Magoules, F.; Meerbergen, K.; Coyette, J.-P., Application of a domain decomposition with Lagrange multipliers to acoustic problems arising from the automotive industry, J. Comput. Acoust., 08, 03, 503-521 (2000) |
| [57] | McInnes, L. C.; Susan-Resiga, R. F.; Keyes, D. E.; Atassi, H. M., Additive Schwarz methods with nonreflecting boundary conditions for the parallel computation of Helmholtz problems, Contemp. Math., 218, 325-333 (1998) · Zbl 0910.65086 |
| [58] | Melenk, J. M.; Sauter, S., Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation, SIAM J. Numer. Anal., 49, 3, 1210-1243 (2011) · Zbl 1229.35038 |
| [59] | A. Modave, X. Antoine, C. Geuzaine, an efficient domain decomposition method with cross-point treatment for Helmholtz problems, 2018. |
| [60] | Moiola, A.; Hiptmair, R.; Perugia, I., Plane wave approximation of homogeneous Helmholtz solutions, Z. Angew. Math. Phys., 62, 5, 809-837 (2011) · Zbl 1263.35070 |
| [61] | Moiola, A.; Spence, E., Is the Helmholtz equation really sign-indefinite?, SIAM Rev., 56, 2, 274-312 (2014) · Zbl 1305.35021 |
| [62] | Mulder, W. A., A multigrid solver for 3D electromagnetic diffusion, Geophys. Prospect., 54, 5, 633-649 (2006) |
| [63] | Nataf, Frédéric; Nier, Francis, Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains, Numer. Math., 75, 3, 357-377 (1997) · Zbl 0873.65108 |
| [64] | Plessix, R.-E., A Helmholtz iterative solver for 3D seismic-imaging problems, Geophysics, 72 (2007), SM185-SM194 |
| [65] | Plessix, R.-E.; Mulder, W. A., Separation-of-variables as a preconditioner for an iterative Helmholtz solver, Appl. Numer. Math., 44, 3, 385-400 (2003) · Zbl 1013.65117 |
| [66] | Poulson, J.; Demanet, L.; Maxwell, N.; Ying, L., A parallel butterfly algorithm, SIAM J. Sci. Comput., 36, 1, C49-C65 (2014) · Zbl 1290.65127 |
| [67] | Poulson, J.; Engquist, B.; Li, S.; Ying, L., A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations, SIAM J. Sci. Comput., 35, 3, C194-C212 (2013) · Zbl 1275.65073 |
| [68] | Pratt, R. G., Seismic waveform inversion in the frequency domain; part 1: theory and verification in a physical scale model, Geophysics, 64, 3, 888-901 (1999) |
| [69] | Rouet, F.-H.; Li, X. S.; Ghysels, P.; Napov, A., A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization, ACM Trans. Math. Softw., 42, 4, 27:1-27:35 (June 2016) · Zbl 1369.65043 |
| [70] | Saad, Y.; Schultz GMRES, M. H., A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (July 1986) · Zbl 0599.65018 |
| [71] | Schwarz, H. A., Uber einen grenzubergang durch alternierendes verfahren, Vierteljahrsschr. Nat.forsch. Ges. Zür., 15, 272-286 (1870) |
| [72] | Sheikh, A. H.; Lahaye, D.; Vuik, C., On the convergence of shifted Laplace preconditioner combined with multilevel deflation, Numer. Linear Algebra Appl., 20, 4, 645-662 (2013) · Zbl 1313.65293 |
| [73] | Sourbier, F.; Haiddar, A.; Giraud, L.; Ben-Hadj-Ali, H.; Operto, S.; Virieux, J., Three-dimensional parallel frequency-domain visco-acoustic wave modelling based on a hybrid direct/iterative solver, Geophys. Prospect., 59, 5, 834-856 (2011) |
| [74] | Spence, E. A., Wavenumber-explicit bounds in time-harmonic acoustic scattering, SIAM J. Math. Anal., 46, 4, 2987-3024 (2014) · Zbl 1302.35139 |
| [75] | Stolk, C. C., A rapidly converging domain decomposition method for the Helmholtz equation, J. Comput. Phys., 241, 0, 240-252 (2013) · Zbl 1349.65426 |
| [76] | Stolk, C. C., A dispersion minimizing scheme for the 3-D Helmholtz equation based on ray theory, J. Comput. Phys., 314, 618-646 (2016) · Zbl 1349.65571 |
| [77] | Stolk, C. C., An improved sweeping domain decomposition preconditioner for the Helmholtz equation, Adv. Comput. Math., 43, 1, 45-76 (Feb 2017) · Zbl 1367.65188 |
| [78] | Taus, M.; Demanet, L.; Zepeda-Núñez, L., A short note on a fast and high-order hybridizable discontinuous Galerkin solver for the 2D high-frequency Helmholtz equation, (SEG Technical Program Expanded Abstracts 2016 (2016)), 3835-3840 |
| [79] | Taus, M.; Demanet, L.; Zepeda-Núñez, L., A short note on a fast and high-order hybridizable discontinuous Galerkin solver for the 2D high-frequency Helmholtz equation, (SEG Technical Program Expanded Abstracts 2016 (2016), Society of Exploration Geophysicists), 3835-3840 |
| [80] | Taus, M.; Zepeda-Núñez, L.; Hewett, R. J.; Demanet, L., L-Sweeps/L-Sweeps-2D (Sep. 2019), version 1.0.0 |
| [81] | Taus, M.; Zepeda-Núñez, L.; Hewett, R. J.; Demanet, L., L-Sweeps/L-Sweeps-2D-examples (Sep. 2019), version 1.0.0 |
| [82] | Matthias Taus, Laurent Demanet, Leonardo Zepeda Núñez, Russell Hewett, Pollution-free and fast hybridizable discontinuous Galerkin solvers for the high-frequency Helmholtz equation, 2017, pp. 4068-4073. |
| [83] | Thakur, R.; Rabenseifner, R.; Gropp, W., Optimization of collective communication operations in mpich, Int. J. High Perform. Comput. Appl., 19, 1, 49-66 (2005) |
| [84] | Toselli, A.; Widlund, O. B., Domain Decomposition Methods — Algorithms and Theory, Springer Series in Computational Mathematics, vol. 34 (2005), Springer: Springer Berlin, Heidelberg · Zbl 1069.65138 |
| [85] | van der, H. A.; Bi-CGSTAB, Vorst, A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 2, 631-644 (1992) · Zbl 0761.65023 |
| [86] | Vion, A.; Geuzaine, C., Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem, J. Comput. Phys., 266, 0, 171-190 (2014) · Zbl 1296.65169 |
| [87] | Virieux, J.; Operto, S., An overview of full-waveform inversion in exploration geophysics, Geophysics, 74, 6 (2009), WCC1-WCC26 |
| [88] | Wang, S.; de Hoop, M. V.; Xia, J.; Li, X. S., Massively parallel structured multifrontal solver for time-harmonic elastic waves in 3-D anisotropic media, Geophys. J. Int., 191, 1, 346-366 (2012) |
| [89] | Xia, J.; Chandrasekaran, S.; Gu, M.; Li, X. S., Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31, 3, 1382-1411 (2010) · Zbl 1195.65031 |
| [90] | Zepeda-Núñez, L.; Demanet, L., A short note on the nested-sweep polarized traces method for the 2D Helmholtz equation, (SEG Technical Program Expanded Abstracts 2015 (2015)), 3682-3687 |
| [91] | Zepeda-Núñez, L.; Demanet, L., The method of polarized traces for the 2D Helmholtz equation, J. Comput. Phys., 308, 347-388 (2016) · Zbl 1351.76197 |
| [92] | Zepeda-Núñez, L.; Demanet, L., Nested domain decomposition with polarized traces for the 2D Helmholtz equation, SIAM J. Sci. Comput., 40, 3, B942-B981 (2018) · Zbl 1394.65136 |
| [93] | Zepeda-Núñez, L.; Zhao, H., Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation, SIAM J. Sci. Comput., 38, 5, B866-B888 (2016) · Zbl 1352.65658 |
| [94] | Zepeda-Núñez, L.; Hewett, R. J.; Demanet, L., Preconditioning the 2D Helmholtz equation with polarized traces, (SEG Technical Program Expanded Abstracts 2014 (2014)), 3465-3470 |
| [95] | Zepeda-Núñez, L.; Scheuer, A.; Hewett, R. J.; Demanet, L., The method of polarized traces for the 3D Helmholtz equation, Geophysics, 84, 4, 1-86 (2019) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
