On the scalability of classical one-level domain-decomposition methods. (English) Zbl 1406.65128
Summary: One-level domain-decomposition methods are in general not scalable, and coarse corrections are needed to obtain scalability. It has however recently been observed in applications in computational chemistry that the classical one-level parallel Schwarz method is surprizingly scalable for the solution of one- and two-dimensional chains of fixed-sized subdomains. We first review some of these recent scalability results of the classical one-level parallel Schwarz method, and then prove similar results for other classical one-level domain-decomposition methods, namely the optimized Schwarz method, the Dirichlet-Neumann method, and the Neumann-Neumann method. We show that the scalability of one-level domain decomposition methods depends critically on the geometry of the domain-decomposition and the boundary conditions imposed on the original problem. We illustrate all our results also with numerical experiments.
MSC:
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65F10 | Iterative numerical methods for linear systems |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
| 70-08 | Computational methods for problems pertaining to mechanics of particles and systems |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
| 35J57 | Boundary value problems for second-order elliptic systems |
Keywords:
domain-decomposition methods; scalability; classical and optimized Schwarz methods; Dirichlet-Neumann method; Neumann-Neumann method; solvation model; chain of atoms; Laplace’s equationReferences:
| [1] | Barone, V.; Cossi, M., Quantum calculation of molecular energies and energy gradients in solution by a conductor solvent model, J. Phys. Chem. A, 102, 1995-2001, (1998) · doi:10.1021/jp9716997 |
| [2] | Bjørstad, PE; Widlund, OB, Iterative methods for the solution of elliptic problems on regions partitioned into substructures, SIAM J. Numer. Anal., 23, 1097-1120, (1986) · Zbl 0615.65113 · doi:10.1137/0723075 |
| [3] | Cancès, E.; Maday, Y.; Stamm, B., Domain decomposition for implicit solvation models, J. Chem. Phys., 139, 054111, (2013) · doi:10.1063/1.4816767 |
| [4] | Chaouqui, F., Gander, M.J.: Optimal coarse spaces for FETI and their approximation. Accepted in ENUMATH 2017 Proceedings (2018) · Zbl 1427.65400 |
| [5] | Chaouqui, Faycal; Gander, Martin J.; Santugini-Repiquet, Kévin, On Nilpotent Subdomain Iterations, 125-133, (2017), Cham · Zbl 1367.65148 |
| [6] | Ciaramella, G.; Gander, MJ, Analysis of the parallel Schwarz method for growing chains of fixed-sized subdomains: Part I, SIAM J. Numer. Anal., 55, 1330-1356, (2017) · Zbl 1366.65111 · doi:10.1137/16M1065215 |
| [7] | Ciaramella, G.; Gander, MJ, Analysis of the parallel Schwarz method for growing chains of fixed-sized subdomains: Part II, SIAM J. Numer. Anal., 56, 1498-1524, (2018) · Zbl 1435.65223 · doi:10.1137/17M1115885 |
| [8] | Ciaramella, Gabriele; Gander, Martin J., Analysis of the parallel Schwarz method for growing chains of fixed-sized subdomains: Part III, ETNA - Electronic Transactions on Numerical Analysis, 49, 210-243, (2018) · Zbl 1404.65301 · doi:10.1553/etna_vol49s210 |
| [9] | Dolean, V.; Gander, MJ; Gerardo-Giorda, L., Optimized Schwarz methods for Maxwell’s equations, SIAM J. Sci. Comput., 31, 2193-2213, (2009) · Zbl 1192.78044 · doi:10.1137/080728536 |
| [10] | Dryja, M., Widlund, O.B.: Multilevel additive methods for elliptic finite element problems. Department of Computer Science, Courant Institute of Mathematical Sciences, New York University (1990) · Zbl 0783.65057 |
| [11] | Dubois, O.; Gander, MJ; Loisel, S.; St-Cyr, A.; Szyld, DB, The optimized Schwarz method with a coarse grid correction, SIAM J. Sci. Comput., 34, a421-a458, (2012) · Zbl 1248.65127 · doi:10.1137/090774434 |
| [12] | Farhat, C.; Lesoinne, M.; Pierson, K., A scalable dual-primal domain decomposition method, Numer. Linear Algebra Appl., 7, 687-714, (2000) · Zbl 1051.65119 · doi:10.1002/1099-1506(200010/12)7:7/8<687::AID-NLA219>3.0.CO;2-S |
| [13] | Gander, MJ, Optimized Schwarz methods, SIAM J. Numer. Anal., 44, 699-731, (2006) · Zbl 1117.65165 · doi:10.1137/S0036142903425409 |
| [14] | Gander, MJ, Schwarz methods over the course of time, Electron. Trans. Numer. Anal., 31, 228-255, (2008) · Zbl 1171.65020 |
| [15] | Gander, MJ; Dubois, O., Optimized Schwarz methods for a diffusion problem with discontinuous coefficient, Numer. Algor., 69, 109-144, (2015) · Zbl 1314.65155 · doi:10.1007/s11075-014-9884-2 |
| [16] | Gander, M.J., Halpern, L.: Méthodes de décomposition de domaine. Encyclopédie électronique pour les ingénieurs (2012) |
| [17] | Gander, Martin J.; Halpern, Laurence; Santugini Repiquet, Kévin, Discontinuous Coarse Spaces for DD-Methods with Discontinuous Iterates, 607-615, (2014), Cham · Zbl 1382.65439 |
| [18] | Gander, Martin J.; Halpern, Laurence; Repiquet, Kévin Santugini, A New Coarse Grid Correction for RAS/AS, 275-283, (2014), Cham · Zbl 1382.65438 |
| [19] | Gander, M.J., Halpern, L., Santugini, K.: On optimal coarse spaces for domain decomposition and their approximation. In: Domain Decomposition Methods in Science and Engineering XXVI. Springer, Berlin (2018) |
| [20] | Gander, Martin J.; Loneland, Atle, SHEM: An Optimal Coarse Space for RAS and Its Multiscale Approximation, 313-321, (2017), Cham · Zbl 1367.65183 |
| [21] | Gander, M.J., Loneland, A., Rahman, T.: Analysis of a new harmonically enriched multiscale coarse space for domain decomposition methods. arXiv:1512.05285 (2015) |
| [22] | Gander, MJ; Magoulès, F.; Nataf, F., Optimized Schwarz methods without overlap for the Helmholtz equation, SIAM J. Sci. Comput., 24, 38-60, (2002) · Zbl 1021.65061 · doi:10.1137/S1064827501387012 |
| [23] | Gander, MJ; Neumüller, M., Analysis of a new space-time parallel multigrid algorithm for parabolic problems, SIAM J. Sci. Comput., 38, a2173-a2208, (2016) · Zbl 1342.65225 · doi:10.1137/15M1046605 |
| [24] | Gander, M.J., Song, B.: Complete, optimal and optimized coarse spaces for additive Schwarz. In: Domain Decomposition Methods in Science and Engineering XXVI. Springer, Berlin (2017) |
| [25] | Gander, M.J., Vanzan, T.: Heterogeneous optimized Schwarz methods for coupling Helmholtz and Laplace equations, accepted in Domain Decomposition Methods in Science and Engineering XXIV (2018) |
| [26] | Gander, M.J., Vanzan, T.: Optimized Schwarz methods for advection diffusion equations in bounded domains, accepted in ENUMATH 2017 Proceedings (2018) · Zbl 1427.65403 |
| [27] | Gander, W., Gander, M.J., Kwok, F.: Scientific Computing—An Introduction Using Maple and MATLAB. Texts in Computational Science and Engineering, vol. 11. Springer, Switzerland (2014) · Zbl 1296.65001 · doi:10.1007/978-3-319-04325-8 |
| [28] | Japhet, C.; Nataf, F.; Rogier, F., The optimized order 2 method: application to convection-diffusion problems, Future Gener. Comput. Syst., 18, 17-30, (2001) · Zbl 1050.65124 · doi:10.1016/S0167-739X(00)00072-8 |
| [29] | Klamt, A.; Schuurmann, G., COSMO: a new approach to dielectric screening in solvents with explicit expressions for the screening energy and its gradient, J. Chem. Soc., Perkin Trans., 2, 799-805, (1993) · doi:10.1039/P29930000799 |
| [30] | Klawonn, A.; Rheinbach, O., Highly scalable parallel domain decomposition methods with an application to biomechanics, ZAMM-J. Appl. Math. Mech., 90, 5-32, (2010) · Zbl 1355.65169 · doi:10.1002/zamm.200900329 |
| [31] | Lions, P.L.: On the Schwarz alternating method. I. In: First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987), pp 1-42. SIAM, Philadelphia (1988) · Zbl 0658.65090 |
| [32] | Lions, P.-L.: On the Schwarz Alternating Method. II. Domain Decomposition Methods (Los Angeles, CA, 1988), pp. 47-70. SIAM, Philadelphia (1989) · Zbl 0681.65072 |
| [33] | Lions, P.-L.: On the Schwarz alternating method. III: a variant for nonoverlapping subdomains. In: Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989), pp 202-223. SIAM, Philadelphia (1990) · Zbl 0704.65090 |
| [34] | Lipparini, F.; Scalmani, G.; Lagardère, L.; Stamm, B.; Cancès, E.; Maday, Y.; Piquemal, J-P; Frisch, MJ; Mennucci, B., Quantum, classical, and hybrid QM/MM calculations in solution: general implementation of the ddCOSMO linear scaling strategy, J. Chem. Phys., 141, 184108, (2014) · doi:10.1063/1.4901304 |
| [35] | Lipparini, F.; Stamm, B.; Cancès, E.; Maday, Y.; Mennucci, B., Fast domain decomposition algorithm for continuum solvation models: energy and first derivatives, J. Chem. Theory Comput., 9, 3637-3648, (2013) · doi:10.1021/ct400280b |
| [36] | Nataf, F., Rogier, F, de Sturler, E.: Optimal interface conditions for domain decomposition methods. Ècolepoly technique (1994) · Zbl 0861.76070 |
| [37] | Nicolaides, RA, Deflation of conjugate gradients with applications to boundary value problems, SIAM J. Numer. Anal., 24, 355-365, (1987) · Zbl 0624.65028 · doi:10.1137/0724027 |
| [38] | Quarteroni, A., Valli, A.: Domain Decomposition Methods for Partial Differential Equations. Numerical Mathematics and Scientific Computation. Clarendon Press, Oxford (1999) · Zbl 0931.65118 |
| [39] | Smith, B., Bjørstad, P., Gropp, W.: Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, Cambridge (2004) · Zbl 0857.65126 |
| [40] | Toselli, A., Widlund, O.: Domain Decomposition Methods—Algorithms and Theory. Springer Series in Computational Mathematics, vol. 34. Springer, Berlin (2005) · Zbl 1069.65138 · doi:10.1007/b137868 |
| [41] | Truong, TN; Stefanovich, EV, A new method for incorporating solvent effect into the classical, ab initio molecular orbital and density functional theory frameworks for arbitrary shape cavity, Chem. Phys. Lett., 240, 253-260, (1995) · doi:10.1016/0009-2614(95)00541-B |
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.
