×

A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods. (English) Zbl 1417.65216

The authors present a class of iterative solvers for the Helmholtz equation. The approach relies on sequential decomposition of the problem in space into a sequence of subproblems, which have in their optimal form the property to lead to nilpotent iterations, like an exact block LU factorization. Using the domain decomposition formulation, the authors present an algorithm for two-dimensional decompositions which is still nilpotent in its optimal form.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F08 Preconditioners for iterative methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Y. Achdou and F. Nataf, {\it Dimension-wise iterated frequency filtering decomposition}, Numer. Linear Algebra Appl., 41 (2003), pp. 1643-1681.
[2] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, {\it A fully asynchronous multifrontal solver using distributed dynamic scheduling}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15-41, . · Zbl 0992.65018
[3] X. Antoine and M. Darbas, {\it Integral equations and iterative schemes for acoustic scattering problems}, in Numerical Methods for Acoustics Problems, F. Magoulès, ed., Saxe-Coburg Publications, 2016, Chapter 2. · Zbl 1064.76095
[4] D. N. Arnold, F. Brezzi, B. Cockburn, and L. D. Marini, {\it Unified analysis of discontinuous Galerkin methods for elliptic problems}, SIAM J. Numer. Anal., 39 (2002), pp. 1749-1779, . · Zbl 1008.65080
[5] I. M. Babu\vska and S. A. Sauter, {\it Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?}, SIAM J. Numer. Anal., 34 (1997), pp. 2392-2423, . · Zbl 0894.65050
[6] H. Bagci, J. E. Pasciak, and K. Y. Sirenko, {\it A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations}, Numer. Linear Algebra Appl., 22 (2015), pp. 371-392. · Zbl 1363.65040
[7] A. Bamberger, P. Joly, and J. E. Roberts, {\it Second-order absorbing boundary conditions for the wave equation: A solution for the corner problem}, SIAM J. Numer. Anal., 27 (1990), pp. 323-352, . · Zbl 0716.35036
[8] L. Banjai and W. Hackbusch, {\it Hierarchical matrix techniques for low- and high-frequency Helmholtz problems}, IMA J. Numer. Anal., 28 (2008), pp. 46-79. · Zbl 1149.78009
[9] M. Bebendorf, {\it Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems}, Springer-Verlag, Berlin, 2008. · Zbl 1151.65090
[10] M. Bebendorf and W. Hackbusch, {\it Existence of \(\mathcal{H} \)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^∞\) coefficients}, Numer. Math., 95 (2003), pp. 1-28. · Zbl 1033.65100
[11] M. Bebendorf, C. Kuske, and R. Venn, {\it Wideband nested cross approximation for Helmholtz problems}, Numer. Math., 130 (2015), pp. 1-34. · Zbl 1317.65242
[12] A. Bendali and Y. Boubendir, {\it Non-overlapping domain decomposition method for a nodal finite element method}, Numer. Math., 103 (2006), pp. 515-537. · Zbl 1099.65122
[13] J.-P. Berenger, {\it A perfectly matched layer for the absorption of electromagnetic waves}, J. Comput. Phys., 114 (1994), pp. 185-200. · Zbl 0814.65129
[14] M. Bollhöfer, M. J. Grote, and O. Schenk, {\it Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media}, SIAM J. Sci. Comput., 31 (2009), pp. 3781-3805, . · Zbl 1203.65273
[15] Y. Boubendir, X. Antoine, and C. Geuzaine, {\it A quasi-optimal non-overlapping domain decomposition algorithm for the Helmholtz equation}, J. Comput. Phys., 231 (2012), pp. 262-280. · Zbl 1243.65144
[16] A. Brandt and I. Livshits, {\it Wave-ray multigrid method for standing wave equations}, Electron. Trans. Numer. Anal., 6 (1997), pp. 162-181. · Zbl 0891.65127
[17] X.-C. Cai, M. A. Casarin, F. W. Elliott, Jr., and O. B. Widlund, {\it Overlapping Schwarz algorithms for solving Helmholtz’s equation}, in Domain Decomposition Methods 10, J. Mandel, C. Farhat, and X.-C. Cai, eds., AMS, 1998, pp. 391-398.
[18] X.-C. Cai and M. Sarkis, {\it A restricted additive Schwarz preconditioner for general sparse linear systems}, SIAM J. Sci. Comput., 21 (1999), pp. 792-797, . · Zbl 0944.65031
[19] X.-C. Cai and O. B. Widlund, {\it Domain decomposition algorithms for indefinite elliptic problems}, SIAM J. Sci. Stat. Comput., 13 (1992), pp. 243-258, . · Zbl 0746.65085
[20] H. Calandra, S. Gratton, X. Pinel, and X. Vasseur, {\it An improved two-grid preconditioner for the solution of three-dimensional Helmholtz problems in heterogeneous media}, Numer. Linear Algebra Appl., 20 (2012), pp. 663-688. · Zbl 1313.65284
[21] S. N. Chandler-Wilde, I. G. Graham, S. Langdon, and E. A. Spence, {\it Numerical-asymptotic boundary integral methods in high-frequency acoustic scattering}, Acta Numer., 21 (2012), pp. 89-305. · Zbl 1257.65070
[22] S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals, {\it A fast solver for HSS representations via sparse matrices}, SIAM J. Matrix Anal., 29 (2006), pp. 67-81, . · Zbl 1135.65317
[23] F. Chaouqui, M. J. Gander, and K. Santugini-Repiquet, {\it On nilpotent subdomain iterations}, in Domain Decomposition Methods in Science and Engineering XXIII, C.-O. Lee, X.-C. Cai, D. E. Keyes, H. H. Kim, A. Klawonn, E.-J. Park, and O. B. Widlund, eds., Springer International, 2017, pp. 125-133. · Zbl 1367.65148
[24] H. Chen, P. Lu, and X. Xu, {\it A robust multilevel method for hybridizable discontinuous Galerkin method for the Helmholtz equation}, J. Comput. Phys., 264 (2014), pp. 133-151. · Zbl 1349.65613
[25] W. Chen, Y. Liu, and X. Xu, {\it A robust domain decomposition method for the Helmholtz equation with high wave number}, ESAIM Math. Model. Numer. Anal., 50 (2016), pp. 921-944. · Zbl 1361.65093
[26] Z. Chen, D. Cheng, W. Feng, T. Wu, and H. Yang, {\it A multigrid-based preconditioned Krylov subspace method for the Helmholtz equation with PML}, J. Math. Anal. Appl., 383 (2011), pp. 522-540. · Zbl 1231.65198
[27] Z. Chen, M. J. Gander, and H. Zhang, {\it On the relation between optimized Schwarz methods and source transfer}, in Domain Decomposition Methods in Science and Engineering XXII, T. Dickopf, M. J. Gander, L. Halpern, R. Krause, and L. F. Pavarino, eds., Springer International, 2016, pp. 217-225. · Zbl 1339.65230
[28] Z. Chen and X. Xiang, {\it A source transfer domain decomposition method for Helmholtz equations in unbounded domain}, SIAM J. Numer. Anal., 51 (2013), pp. 2331-2356, . · Zbl 1285.65082
[29] Z. Chen and X. Xiang, {\it A source transfer domain decomposition method for Helmholtz equations in unbounded domain, Part II: Extensions}, Numer. Math. Theory Methods Appl., 6 (2013), pp. 538-555. · Zbl 1299.65287
[30] P. Chevalier and F. Nataf, {\it Symmetrized method with optimized second-order conditions for the Helmholtz equation}, in Domain Decomposition Methods 10, J. Mandel, C. Farhat, and X.-C. Cai, eds., AMS, 1998, pp. 400-407. · Zbl 0909.65105
[31] W.-C. Chew, J.-M. Jin, and E. Michielssen, {\it Complex coordinate stretching as a generalized absorbing boundary condition}, Microw. Opt. Technol. Lett., 15 (1997), pp. 363-369.
[32] P.-H. Cocquet and M. J. Gander, {\it How large a shift is needed in the shifted Helmholtz preconditioner for its effective inversion by multigrid?}, SIAM J. Sci. Comput., 39 (2017), pp. A438-A478, . · Zbl 1365.65269
[33] F. Collino, {\it High order absorbing boundary conditions for wave propagation models: Straight line boundary and corner cases}, in Proceedings of the Second International Conference on Mathematical and Numerical Aspects of Wave Propagation, R. Kleinman et al., eds., SIAM. 1993, pp. 161-171. · Zbl 0814.35065
[34] F. Collino, S. Ghanemi, and P. Joly, {\it Domain decomposition method for harmonic wave propagation: A general presentation}, Comput. Methods Appl. Mech. Engrg., 184 (2000), pp. 171-211. · Zbl 0965.65134
[35] L. Conen, V. Dolean, R. Krause, and F. Nataf, {\it A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator}, J. Comput. Appl. Math., 271 (2014), pp. 83-99. · Zbl 1321.65172
[36] S. Cools, B. Reps, and W. Vanroose, {\it A new level-dependent coarse grid correction scheme for indefinite Helmholtz problems}, Numer. Linear Algebra Appl., 21 (2014), pp. 513-533. · Zbl 1340.65294
[37] S. Cools and W. Vanroose, {\it Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems}, Numer. Linear Algebra Appl., 20 (2013), pp. 575-597. · Zbl 1313.65320
[38] T. A. Davis, {\it Algorithm 832: UMFPACK, an unsymmetric-pattern multifrontal method}, ACM Trans. Math. Software, 30 (2004), pp. 196-199. · Zbl 1072.65037
[39] T. A. Davis, {\it Direct Methods for Sparse Linear Systems}, SIAM, 2006, . · Zbl 1119.65021
[40] A. de La Bourdonnaye, C. Farhat, A. Macedo, F. Magoulès, and F.-X. Roux, {\it A non-overlapping domain decomposition method for the exterior Helmholtz problem}, in Domain Decomposition Methods 10, J. Mandel, C. Farhat, and X.-C. Cai, eds., AMS, 1998, pp. 42-66. · Zbl 0909.65103
[41] B. Després, {\it Méthodes de Décomposition de Domaine pour les Problémes de Propagation d’Ondes en Régime Harmonique}, Ph.D. thesis, Université Dauphine, Paris, 1991. · Zbl 0849.65085
[42] V. Dolean, P. Jolivet, and F. Nataf, {\it An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation}, SIAM, 2015, . · Zbl 1364.65277
[43] J. Douglas, Jr. and D. B. Meade, {\it Second-order transmission conditions for the Helmholtz equation}, in Ninth International Conference on Domain Decomposition Methods, P. E. Bjorstad, M. S. Espedal, and D. E. Keyes, eds., DDM.org, 1998, pp. 434-441.
[44] V. Druskin, S. Güttel, and L. Knizhnerman, {\it Near-optimal perfectly matched layers for indefinite Helmholtz problems}, SIAM Rev., 58 (2016), pp. 90-116, . · Zbl 1344.35009
[45] V. Druskin and L. Knizhnerman, {\it Gaussian spectral rules for the three-point second differences: I. A two-point positive definite problem in a semi-infinite domain}, SIAM J. Numer. Anal., 37 (1999), pp. 403-422, . · Zbl 0947.65127
[46] M. Dryja and O. B. Widlund, {\it An Additive Variant of the Schwarz Alternating Method for the Case of Many Subregions}, Tech. Report 339, also Ultracomputer Note 131, Department of Computer Science, Courant Institute, 1987.
[47] I. S. Duff, A. M. Erisman, and J. K. Reid, {\it Direct Methods for Sparse Matrices}, Oxford University Press, 1986. · Zbl 0604.65011
[48] E. Efstathiou and M. J. Gander, {\it Why restricted additive Schwarz converges faster than additive Schwarz}, BIT, 43 (2003), pp. 945-959. · Zbl 1045.65027
[49] B. Engquist and A. Majda, {\it Absorbing boundary conditions for the numerical simulation of waves}, Math. Comp., 31 (1977), pp. 629-651. · Zbl 0367.65051
[50] B. Engquist and A. Majda, {\it Radiation boundary conditions for acoustic and elastic wave calculations}, Comm. Pure Appl. Math., 32 (1979), pp. 313-357. · Zbl 0387.76070
[51] B. Engquist and L. Ying, {\it Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation}, Comm. Pure Appl. Math., 64 (2011), pp. 697-735. · Zbl 1229.35037
[52] B. Engquist and L. Ying, {\it Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers}, Multiscale Model. Simul., 9 (2011), pp. 686-710, . · Zbl 1228.65234
[53] B. Engquist and H. Zhao, {\it Absorbing boundary conditions for domain decomposition}, Appl. Numer. Math., 27 (1998), pp. 341-365. · Zbl 0935.65135
[54] B. Engquist and H. Zhao, {\it Approximate separability of Green’s function of the Helmholtz equation in the high-frequency limit}, Comm. Pure Appl. Math., 71 (2018), pp. 2220-2274. · Zbl 1405.35022
[55] Y. A. Erlangga, {\it Advances in iterative methods and preconditioners for the Helmholtz equation}, Arch. Comput. Methods Eng., 15 (2008), pp. 37-66. · Zbl 1158.65078
[56] Y. A. Erlangga and R. Nabben, {\it On a multilevel Krylov method for the Helmholtz equation preconditioned by shifted Laplacian}, Electron. Trans. Numer. Anal., 31 (2008), pp. 403-424. · Zbl 1190.65050
[57] Y. A. Erlangga, C. W. Oosterlee, and C. Vuik, {\it A novel multigrid based preconditioner for heterogeneous Helmholtz problems}, SIAM J. Sci. Comput., 27 (2006), pp. 1471-1492, . · Zbl 1095.65109
[58] Y. A. Erlangga, C. Vuik, and C. W. Oosterlee, {\it On a class of preconditioners for the Helmholtz equation}, Appl. Numer. Math., 50 (2004), pp. 409-425. · Zbl 1051.65101
[59] O. Ernst and M. J. Gander, {\it Why it is difficult to solve Helmholtz problems with classical iterative methods}, in Numerical Analysis of Multiscale Problems, I. Graham, T. Hou, O. Lakkis, and R. Scheichl, eds., Springer-Verlag, 2012, pp. 325-363. · Zbl 1248.65128
[60] M. Eslaminia and M. N. Guddati, {\it A double-sweeping preconditioner for the Helmholtz equation}, J. Comput. Phys., 314 (2016), pp. 800-823. · Zbl 1349.65109
[61] C. Farhat, P. Avery, R. Tezaur, and J. Li, {\it FETI-DPH: A dual-primal domain decomposition method for acoustic scattering}, J. Comput. Acoust., 13 (2005), pp. 499-524. · Zbl 1189.76338
[62] C. Farhat, A. Macedo, M. Lesoinne, F.-X. Roux, F. Magoulès, and A. D. L. Bourdonnaie, {\it Two-level domain decomposition methods with Lagrange multipliers for the fast iterative solution of acoustic scattering problems}, Comput. Methods Appl. Mech. Engrg., 184 (2000), pp. 213-239. · Zbl 0979.76046
[63] C. Farhat and F.-X. Roux, {\it Implicit parallel processing in structural mechanics}, Comput. Mech. Adv., 2 (1994), pp. 1-124. · Zbl 0805.73062
[64] M. J. Gander, {\it Optimized Schwarz methods}, SIAM J. Numer. Anal., 44 (2006), pp. 699-731, . · Zbl 1117.65165
[65] M. J. Gander, {\it Schwarz methods over the course of time}, Electron. Trans. Numer. Anal., 31 (2008), pp. 228-255. · Zbl 1171.65020
[66] M. J. Gander, I. G. Graham, and E. A. Spence, {\it Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?}, Numer. Math., 131 (2015), pp. 567-614. · Zbl 1328.65238
[67] M. J. Gander and S. Hajian, {\it Analysis of Schwarz methods for a hybridizable discontinuous Galerkin discretization}, SIAM J. Numer. Anal., 53 (2015), pp. 573-597, . · Zbl 1312.65190
[68] M. J. Gander and L. Halpern, {\it Méthodes de décomposition de domaine}, Encyclopédie électronique pour les ingénieurs, 2012.
[69] M. J. Gander, L. Halpern, and F. Magoulès, {\it An optimized Schwarz method with two-sided Robin transmission conditions for the Helmholtz equation}, Internat. J. Numer. Methods Fluids, 55 (2007), pp. 163-175. · Zbl 1125.65114
[70] M. J. Gander, L. Halpern, and K. Santugini-Repiquet, {\it Discontinuous coarse spaces for DD-methods with discontinuous iterates}, in Domain Decomposition Methods in Science and Engineering XXI, J. Erhel, M. J. Gander, L. Halpern, G. Pichot, T. Sassi, and O. Widlund, eds., Springer, 2014, pp. 607-615. · Zbl 1382.65439
[71] M. J. Gander, L. Halpern, and K. Santugini-Repiquet, {\it A new coarse grid correction for RAS/AS}, in Domain Decomposition Methods in Science and Engineering XXI, J. Erhel, M. J. Gander, L. Halpern, G. Pichot, T. Sassi, and O. Widlund, eds., Springer, 2014, pp. 275-283. · Zbl 1382.65438
[72] M. J. Gander and F. Kwok, {\it Optimal interface conditions for an arbitrary decomposition into subdomains}, in Domain Decomposition Methods in Science and Engineering XIX, Y. Huang, R. Kornhuber, O. Widlund, and J. Xu, eds., Heidelberg, 2010, Springer-Verlag, pp. 101-108. · Zbl 1217.65223
[73] M. J. Gander and F. Kwok, {\it Best Robin parameters for optimized Schwarz methods at cross points}, SIAM J. Sci. Comput., 34 (2012), pp. A1849-A1879, . · Zbl 1254.65126
[74] M. J. Gander and A. Loneland, {\it SHEM: An optimal coarse space for RAS and its multiscale approximation}, in Domain Decomposition Methods in Science and Engineering XXIII, C.-O. Lee, X.-C. Cai, D. E. Keyes, H. H. Kim, A. Klawonn, E.-J. Park, and O. B. Widlund, eds., Springer International, 2017, pp. 313-321. · Zbl 1367.65183
[75] M. J. Gander, A. Loneland, and T. Rahman, {\it Analysis of a New Harmonically Enriched Multiscale Coarse Space for Domain Decomposition Methods}, preprint, , 2015.
[76] M. J. Gander, F. Magoulès, and F. Nataf, {\it Optimized Schwarz methods without overlap for the Helmholtz equation}, SIAM J. Sci. Comput., 24 (2002), pp. 38-60, . · Zbl 1021.65061
[77] M. J. Gander and F. Nataf, {\it AILU: A preconditioner based on the analytic factorization of the elliptic operator}, Numer. Linear Algebra Appl., 7 (2000), pp. 505-526. · Zbl 1051.65054
[78] M. J. Gander and F. Nataf, {\it An incomplete LU preconditioner for problems in acoustics}, J. Comput. Acoust., 13 (2005), pp. 455-476. · Zbl 1189.76362
[79] M. J. Gander and Y. Xu, {\it Optimized Schwarz methods for circular domain decompositions with overlap}, SIAM J. Numer. Anal., 52 (2014), pp. 1981-2004, . · Zbl 1304.65261
[80] M. J. Gander and Y. Xu, {\it Optimized Schwarz methods with nonoverlapping circular domain decomposition}, Math. Comp., 86 (2016), pp. 637-660. · Zbl 1355.65167
[81] M. J. Gander and H. Zhang, {\it Domain decomposition methods for the Helmholtz equation: A numerical investigation}, in Domain Decomposition Methods in Science and Engineering XX, R. Bank, M. Holst, O. Widlund, and J. Xu, eds., Springer-Verlag, 2013, pp. 215-222.
[82] M. J. Gander and H. Zhang, {\it Algorithmic perspective of PML transmission conditions for domain decomposition methods}, in 2014 IEEE Conference on Antenna Measurements Applications, 2014, .
[83] M. J. Gander and H. Zhang, {\it Optimized Schwarz methods with overlap for the Helmholtz equation}, in Domain Decomposition Methods in Science and Engineering XXI, J. Erhel, M. J. Gander, L. Halpern, G. Pichot, T. Sassi, and O. Widlund, eds., Springer-Verlag, 2014, pp. 207-214.
[84] M. J. Gander and H. Zhang, {\it Optimized Schwarz methods with overlap for the Helmholtz equation}, SIAM J. Sci. Comput., 38 (2016), pp. A3195-A3219, . · Zbl 1351.65094
[85] M. J. Gander and H. Zhang, {\it Restrictions on the use of sweeping type preconditioners for Helmholtz problems}, in Domain Decomposition Methods in Science and Engineering XXIV, P. E. Bjorstad, S. C. Brenner, L. Halpern, R. Kornhuber, H. H. Kim, T. Rahman, and O. B. Widlund, eds., Springer, 2018, pp. 325-336. · Zbl 1450.65159
[86] A. George, {\it Nested dissection of a regular finite element mesh}, SIAM J. Numer. Anal., 10 (1973), pp. 345-363, . · Zbl 0259.65087
[87] S. Ghanemi, {\it A domain decomposition method for Helmholtz scattering problems}, in Ninth International Conference on Domain Decomposition Methods, P. E. Bjorstad, M. S. Espedal, and D. E. Keyes, eds., DDM.org, 1998, pp. 105-112.
[88] A. Gillman and P.-G. Martinsson, {\it An \(O(N)\) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads}, Adv. Comput. Math., 40 (2014), pp. 773-796. · Zbl 1295.65107
[89] D. Gordon and R. Gordon, {\it Robust and highly scalable parallel solution of the Helmholtz equation with large wave numbers}, J. Comput. Appl. Math., 237 (2013), pp. 182-196. · Zbl 1252.65181
[90] I. G. Graham, E. A. Spence, and E. Vainikko, {\it Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption}, in Modern Solvers for Helmholtz Problems, D. Lahaye, J. Tang, and K. Vuik, eds., Springer International, 2017, pp. 3-26. · Zbl 1366.65113
[91] A. Greenbaum, {\it Iterative Methods for Solving Linear Systems}, SIAM, 1997, . · Zbl 0883.65022
[92] M. N. Guddati and J. L. Tassoulas, {\it Continued-fraction absorbing boundary conditions for the wave equation}, J. Comput. Acoust., 8 (2000), pp. 139-156. · Zbl 1360.76136
[93] W. Hackbusch, {\it A sparse matrix arithmetic based on \(\mathcal{H} \)-matrices, Part I: Introduction to \(\mathcal{H} \)-matrices}, Computing, 62 (1999), pp. 89-108. · Zbl 0927.65063
[94] W. Hackbusch, {\it A sparse \(\mathcal{H} \)-matrix arithmetic, Part II: Application to multi-dimensional problems}, Computing, 64 (2000), pp. 21-47. · Zbl 0962.65029
[95] W. Hackbusch, {\it Hierarchical Matrices: Algorithms and Analysis}, Springer-Verlag, 2015. · Zbl 1336.65041
[96] T. Hagstrom, {\it Radiation boundary conditions for the numerical simulation of waves}, Acta Numer., 8 (1999), pp. 47-106. · Zbl 0940.65108
[97] T. Hagstrom and S. I. Hariharan, {\it A formulation of asymptotic and exact boundary conditions using local operators}, Appl. Numer. Math., 27 (1998), pp. 403-416. · Zbl 0924.35167
[98] T. Hagstrom, R. P. Tewarson, and A. Jazcilevich, {\it Numerical experiments on a domain decomposition algorithm for nonlinear elliptic boundary value problems}, Appl. Math. Lett., 1 (1988), pp. 299-302. · Zbl 0656.65097
[99] L. Halpern, S. Petit-Bergez, and J. Rauch, {\it The analysis of matched layers}, Confluentes Math., 3 (2011), pp. 159-236. · Zbl 1263.65088
[100] L. Halpern and L. N. Trefethen, {\it Wide-angle one-way wave equations}, J. Acoust. Soc. Amer., 84 (1988), pp. 1397-1404.
[101] H. Han and X. Wu, {\it Artificial Boundary Method}, Tsinghua University Press, Springer-Verlag, 2013. · Zbl 1277.65105
[102] J. Henry, L. Bento, and M. Soares, {\it Factorization of linear elliptic boundary value problems in non-cylindrical domains}, C. R. Acad. Sci. Paris Ser. I, 349 (2011), pp. 879-882. · Zbl 1225.35063
[103] K. L. Ho and L. Greengard, {\it A fast direct solver for structured linear systems by recursive skeletonization}, SIAM J. Sci. Comput., 34 (2012), pp. A2507-A2532, . · Zbl 1259.65062
[104] A. J. Hoffman, M. S. Martin, and D. J. Rose, {\it Complexity bounds for regular finite difference and finite element grids}, SIAM J. Numer. Anal., 10 (1973), pp. 364-369, . · Zbl 0261.65026
[105] Q. Hu and X. Li, {\it Efficient multilevel preconditioners for three-dimensional plane wave Helmholtz systems with large wave numbers}, Multiscale Model. Simul., 15 (2017), pp. 1242-1266, .
[106] F. Ihlenburg and I. Babu\vska, {\it Finite element solution of the Helmholtz equation with high wave number. Part I: The \(h\)-version of the FEM}, Comput. Math. Appl., 30 (1995), pp. 9-37. · Zbl 0838.65108
[107] K. Ito and J. Toivanen, {\it Preconditioned iterative methods on sparse subspaces}, Appl. Math. Lett., 19 (2006), pp. 1191-1197. · Zbl 1176.65030
[108] B. N. Khoromskij and G. Wittum, {\it Numerical Solution of Elliptic Differential Equations by Reduction to the Interface}, Springer-Verlag, 2004. · Zbl 1043.65128
[109] S. Kim and M. Lee, {\it Artificial damping techniques for scalar waves in the frequency domain}, Comput. Math. Appl., 31 (1996), pp. 1-12. · Zbl 0855.65127
[110] S. Kim and H. Zhang, {\it Optimized Schwarz method with complete radiation transmission conditions for the Helmholtz equation in waveguides}, SIAM J. Numer. Anal., 53 (2015), pp. 1537-1558, . · Zbl 1327.78025
[111] S. Kim and H. Zhang, {\it Optimized double sweep Schwarz method by complete radiation boundary conditions}, Comput. Math. Appl., 72 (2016), pp. 1573-1589. · Zbl 1359.65291
[112] R. Kress, {\it Scattering by obstacles}, in Scattering: Scattering and Inverse Scattering in Pure and Applied Science, R. Pike and P. Sabatier, eds., Academic Press, 2002, pp. 191-210.
[113] F. Kwok, {\it Optimized additive Schwarz with harmonic extension as a discretization of the continuous parallel Schwarz method}, SIAM J. Numer. Anal., 49 (2011), pp. 1289-1316, . · Zbl 1263.65128
[114] R. F. Lago, {\it A Study on Block Flexible Iterative Solvers with Applications to Earth Imaging Problem in Geophysics}, Ph.D. thesis, CERFACS, Toulouse, 2013.
[115] P. Le Tallec, {\it Domain decomposition methods in computational mechanics}, Comput. Mech. Adv., 1 (1994), pp. 121-220. · Zbl 0802.73079
[116] J. Li and X. Tu, {\it Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems}, Numer. Linear Algebra Appl., 16 (2009), pp. 745-773. · Zbl 1224.65248
[117] X. S. Li, {\it An overview of SuperLU: Algorithms, implementation, and user interface}, ACM Trans. Math. Softw., 31 (2005), pp. 302-325. · Zbl 1136.65312
[118] P.-L. Lions, {\it On the Schwarz alternating method. I}, in First International Symposium on Domain Decomposition Methods for Partial Differential Equations, R. Glowinski, G. H. Golub, G. A. Meurant, and J. Périaux, eds., SIAM, 1988, pp. 1-42. · Zbl 0658.65090
[119] F. Liu and L. Ying, {\it Additive sweeping preconditioner for the Helmholtz equation}, Multiscale Model. Simul., 14 (2016), pp. 799-822, . · Zbl 1338.65077
[120] F. Liu and L. Ying, {\it Recursive sweeping preconditioner for the three-dimensional Helmholtz equation}, SIAM J. Sci. Comput., 38 (2016), pp. A814-A832, . · Zbl 1376.65035
[121] F. Liu and L. Ying, {\it Sparsify and sweep: An efficient preconditioner for the Lippmann-Schwinger equation}, SIAM J. Sci. Comput., 40 (2018), pp. B379-B404, . · Zbl 1392.65035
[122] H. Liu, {\it The Nine Chapters on the Mathematical Art: Companion and Commentary}, Oxford University Press, Science Press, Beijing, 1999 (originally written in 263 ad).
[123] I. Livshits, {\it The least squares AMG solver for the one-dimensional Helmholtz operator}, Comput. Vis. Sci., 14 (2011), pp. 17-25. · Zbl 1241.65068
[124] S. Loisel, {\it Condition number estimates for the nonoverlapping optimized Schwarz method and the \(2\)-Lagrange multiplier method for general domains and cross points}, SIAM J. Numer. Anal., 51 (2013), pp. 3062-3083, . · Zbl 1287.35003
[125] Y. Y. Lu, {\it Some techniques for computing wave propagation in optical waveguides}, Commun. Comput. Phys., 1 (2006), pp. 1056-1075. · Zbl 1116.78030
[126] P.-G. Martinsson and V. Rokhlin, {\it A fast direct solver for boundary integral equations in two dimensions}, J. Comput. Phys., 205 (2005), pp. 1-23. · Zbl 1078.65112
[127] P.-G. Martinsson and V. Rokhlin, {\it A fast direct solver for scattering problems involving elongated structures}, J. Comput. Phys., 221 (2007), pp. 288-302. · Zbl 1111.65109
[128] L. C. McInnes, R. F. Susan-Resiga, D. E. Keyes, and H. M. Atassi, {\it Additive Schwarz methods with nonreflecting boundary conditions for the parallel computation of Helmholtz problems}, in Domain Decomposition Methods 10, J. Mandel, C. Farhat, and X.-C. Cai, eds., AMS, 1998, pp. 325-333. · Zbl 0910.65086
[129] F. Nataf, {\it On the Use of Open Boundary Conditions in Block Gauss-Seidel Methods for Convection-Diffusion Equations}, Tech. Report, CMAP (École Polytechnique), 1993.
[130] F. Nataf and F. Nier, {\it Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains}, Numer. Math., 75 (1997), pp. 357-377. · Zbl 0873.65108
[131] F. Nataf and F. Rogier, {\it Factorization of the convection-diffusion operator and the Schwarz algorithm}, Math. Models Methods Appl. Sci., 5 (1995), pp. 67-93. · Zbl 0826.65102
[132] F. Nataf, F. Rogier, and E. de Studer, {\it Domain decomposition methods for fluid dynamics}, in Navier-Stokes Equations and Related Nonlinear Analysis, A. Sequeira, ed., Plenum Press, 1995, pp. 367-376. · Zbl 0861.76070
[133] F. Nataf, F. Rogier, and E. de Sturler, {\it Optimal Interface Conditions for Domain Decomposition Methods}, Tech. Report, CMAP (École Polytechnique), 1994. · Zbl 0861.76070
[134] J.-C. Nédélec, {\it Acoustic and Electromagnetic Equations: Integral Representations for Harmonic Problems}, Springer-Verlag, 2001. · Zbl 0981.35002
[135] F. Nier, {\it Remarques sur les algorithmes de décomposition de domaines}, Sémin. Équ. Dériv. Partielles, École Polytech., Palaiseau, 1999, pp. 1-24. · Zbl 1058.65514
[136] L. N. Olson and J. B. Schroder, {\it Smoothed aggregation for Helmholtz problems}, Numer. Linear Algebra Appl., 17 (2010), pp. 361-386. · Zbl 1240.65359
[137] H. Poincaré, {\it La méthode de Neumann et le probléme de Dirichlet}, Acta Math., 20 (1895), pp. 59-142. · JFM 27.0316.01
[138] J. Popovic and O. Runborg, {\it Analysis of a fast method for solving the high frequency Helmholtz equation in one dimension}, BIT, 51 (2011), pp. 721-755. · Zbl 1260.65067
[139] J. Poulson, S. Engquist, S. Li, and L. Ying, {\it A parallel sweeping preconditioner for heterogeneous {\it 3}D Helmholtz equations}, SIAM J. Sci. Comput., 35 (2013), pp. C194-C212, . · Zbl 1275.65073
[140] L. Qin and X. Xu, {\it On a parallel Robin-type nonoverlapping domain decomposition method}, SIAM J. Numer. Anal., 44 (2006), pp. 2539-2558, . · Zbl 1131.65098
[141] A. Quateroni and A. Valli, {\it Domain Decomposition Methods for Partial Differential Equations}, Calderon Press, 1999.
[142] A. G. Ramm, {\it Fundamental solutions to some elliptic equations with discontinuous senior coefficients and an inequality for these solutions}, Math. Inequal. Appl., 1 (1998), pp. 99-104. · Zbl 0888.35032
[143] L. F. Richardson, {\it The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam}, Philos. Trans. Roy. Soc. London Ser. A, 210 (1911), pp. 307-357. · JFM 42.0873.02
[144] C. D. Riyanti, A. Kononov, Y. A. Erlangga, C. Vuik, C. W. Oosterlee, R.-E. Plessix, and W. A. Mulder, {\it A parallel multigrid-based preconditioner for the 3D heterogeneous high-frequency Helmholtz equation}, J. Comput. Phys., 224 (2007), pp. 431-448. · Zbl 1120.65127
[145] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, 2003, . · Zbl 1031.65046
[146] M. Sarkis and D. B. Szyld, {\it Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms}, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1612-1621. · Zbl 1173.65366
[147] F. Sauvigny, {\it Partial Differential Equations} 2, 2nd ed., Springer-Verlag, 2012, pp. 248-257.
[148] A. Schädle and L. Zschiedrich, {\it Additive Schwarz method for scattering problems using the PML method at interfaces}, in Domain Decomposition Methods in Science and Engineering XVI, O. Widlund and D. E. Keyes, eds., Springer-Verlag, 2007, pp. 205-212.
[149] A. Schädle, L. Zschiedrich, S. Burger, R. Klose, and F. Schmidt, {\it Domain decomposition method for Maxwell’s equations: Scattering off periodic structures}, J. Comput. Phys., 226 (2007), pp. 477-493. · Zbl 1310.78009
[150] O. Schenk, M. Bollhöfer, and R. A. Römer, {\it On large-scale diagonalization techniques for the Anderson model of localization}, SIAM Rev., 50 (2008), pp. 91-112, . · Zbl 1136.65044
[151] H. A. Schwarz, {\it Über einen Grenzübergang durch alternierendes Verfahren}, Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich, 15 (1870), pp. 272-286.
[152] A. H. Sheikh, D. Lahaye, and C. Vuik, {\it On the convergence of shifted Laplace preconditioner combined with multilevel deflation}, Numer. Linear Algebra Appl., 20 (2013), pp. 645-662. · Zbl 1313.65293
[153] B. Smith, P. E. Bjorstad, and W. D. Gropp, {\it Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations}, Cambridge University Press, 1996. · Zbl 0857.65126
[154] A. Sommerfeld, {\it Partial Differential Equations in Physics}, Academic Press, 1949. · Zbl 0034.35702
[155] A. St-Cyr, M. J. Gander, and S. J. Thomas, {\it Optimized multiplicative, additive, and restricted additive Schwarz preconditioning}, SIAM J. Sci. Comput., 29 (2007), pp. 2402-2425, . · Zbl 1154.65017
[156] V. A. Steklov, {\it General Methods for the Solution of Principal Mathematical Physics Problems}, Kharkov Mathematical Society, 1901.
[157] C. C. Stolk, {\it A rapidly converging domain decomposition method for the Helmholtz equation}, J. Comput. Phys., 241 (2013), pp. 240-252. · Zbl 1349.65426
[158] C. C. Stolk, {\it An improved sweeping domain decomposition preconditioner for the Helmholtz equation}, Adv. Comput. Math., 43 (2017), pp. 45-76. · Zbl 1367.65188
[159] C. C. Stolk, M. Ahmed, and S. K. Bhowmik, {\it A multigrid method for the Helmholtz equation with optimized coarse grid corrections}, SIAM J. Sci. Comput., 36 (2014), pp. A2819-A2841, . · Zbl 1310.65157
[160] B. Stupfel, {\it Improved transmission conditions for a one-dimensional domain decomposition method applied to the solution of the Helmholtz equation}, J. Comput. Phys., 229 (2010), pp. 851-874. · Zbl 1184.78081
[161] S. Ta’asan, {\it Multigrid Methods for Highly Oscillatory Problems}, Ph.D. thesis, Weizmann Institute of Science, Rehovot, Israel, 1984.
[162] A. Taflove and S. C. Hagness, {\it Computational Electrodynamics: The Finite Difference Time-Domain Method}, 3rd ed., Artech House, 2005. · Zbl 0963.78001
[163] A. Toselli, {\it Overlapping methods with perfectly matched layers for the solution of the Helmholtz equation}, in Eleventh International Conference on Domain Decomposition Methods, C. Lai, P. Bjorstad, M. Cross, and O. Widlund, eds., DDM.org, 1999, pp. 551-558.
[164] A. Toselli and O. Widlund, {\it Domain Decomposition Methods: Algorithms and Theory}, Springer-Verlag, 2005. · Zbl 1069.65138
[165] L. N. Trefethen, {\it The Definition of Numerical Analysis}, Tech. Report TR 92-1304, Cornell University, 1992.
[166] L. N. Trefethen and L. Halpern, {\it Well-posedness of one-way wave equations and absorbing boundary conditions}, Math. Comp., 47 (1986), pp. 421-435. · Zbl 0618.65077
[167] M. B. van Gijzen, Y. A. Erlangga, and C. Vuik, {\it Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian}, SIAM J. Sci. Comput., 29 (2007), pp. 1942-1958, . · Zbl 1155.65088
[168] P. Vanek, J. Mandel, and M. Brezina, {\it Two-level algebraic multigrid for the Helmholtz problem}, in Domain Decomposition Methods 10, J. Mandel, C. Farhat, and X.-C. Cai, eds., AMS, 1998, pp. 349-356. · Zbl 0910.65087
[169] A. Vion and C. Geuzaine, {\it Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem}, J. Comput. Phys., 266 (2014), pp. 171-190. · Zbl 1296.65169
[170] S. Wang, M. V. de Hoop, and J. Xia, {\it Acoustic inverse scattering via Helmholtz operator factorization and optimization}, J. Comput. Phys., 229 (2010), pp. 8445-8462. · Zbl 1201.65193
[171] S. Wang, M. V. de Hoop, and J. Xia, {\it On {\it 3}D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver}, Geophys. Prospecting, 59 (2011), pp. 857-873.
[172] S. Wang, X. S. Li, J. Xia, Y. Situ, and M. V. de Hoop, {\it Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures}, SIAM J. Sci. Comput., 35 (2013), pp. C519-C544, . · Zbl 1285.65017
[173] C. Weisbecker, P. Amestoy, O. Boiteau, R. Brossier, A. Buttari, J.-Y. L’Excellent, S. Operto, and J. Virieux, {\it{\it 3}D frequency-domain seismic modeling with a block low-rank algebraic multifrontal direct solver}, in SEG Houston 2013, 2013, pp. 3411-3416.
[174] T. H. Wolff, {\it Recent work on sharp estimates in second-order elliptic unique continuation problems}, J. Geometric Anal., 3 (1993), pp. 621-650. · Zbl 0787.35017
[175] J. Xia, {\it Efficient structured multifrontal factorization for general large sparse matrices}, SIAM J. Sci. Comput., 35 (2013), pp. A832-A860, . · Zbl 1266.15022
[176] L. Ying, {\it Sparsifying preconditioner for the Lippmann-Schwinger equation}, Multiscale Model. Simul., 13 (2015), pp. 644-660, . · Zbl 1317.65087
[177] E. Zauderer, {\it Partial Differential Equations of Applied Mathematics}, 3rd ed., Pure Appl. Math. 71, John Wiley & Sons, 2011. · Zbl 0551.35002
[178] L. Zepeda-Nún͂ez and L. Demanet, {\it Nested domain decomposition with polarized traces for the {\it 2}D Helmholtz equation}, SIAM J. Sci. Comput., 40 (2018), pp. B942-B981, . · Zbl 1394.65136
[179] L. Zepeda-Nún͂ez and L. Demanet, {\it The method of polarized traces for the {\it 2}D Helmholtz equation}, J. Comput. Phys., 308 (2016), pp. 347-388. · Zbl 1351.76197
[180] L. Zepeda-Nún͂ez, R. J. Hewett, and L. Demanet, {\it Preconditioning the {\it 2}D Helmholtz equation with polarized traces}, in SEG Technical Program Expanded Abstracts 2014, SEG, 2014, pp. 3465-3470.
[181] L. Zepeda-Nún͂ez and H. Zhao, {\it Fast alternating bidirectional preconditioner for the {\it 2}D high-frequency Lippmann-Schwinger equation}, SIAM J. Sci. Comput., 38 (2016), pp. B866-B888, .
[182] L. Zhu and H. Wu, {\it Preasymptotic error analysis of CIP-FEM and FEM for Helmholtz equation with high wave number. Part II: \(hp\) version}, SIAM J. Numer. Anal., 51 (2013), pp. 1828-1852, . · Zbl 1416.65468
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.