Methods of Reflections: relations with Schwarz methods and classical stationary iterations, scalability and preconditioning.
Gabriele Ciaramella; Martin J. Gander; Laurence Halpern; Julien Salomon
The SMAI journal of computational mathematics, Volume 5  (2019), p. 161-193

The basic idea of the method of reflections appeared almost two hundred years ago; it is a method of successive approximations for the interaction of particles within a fluid, and it seems intuitively related to the Schwarz domain decomposition methods, the subdomains being the complements of the particle domains. We show in this paper that indeed there is a direct correspondence between the methods of reflections and Schwarz methods in the two particle/subdomain case. This allows us to give a new convergence analysis based on maximum principle techniques with precise convergence estimates that one could not obtain otherwise. We then show however also that in the case of more than two particles/subdomains, the methods of reflections and the Schwarz methods are really different methods, with different convergence properties. Using substructuring techniques from domain decomposition, we then show that the methods of reflections are classical block Jacobi and block Gauss-Seidel methods for the interface traces, and we derive new, relaxed versions of the methods of reflections with better convergence properties. We finally also introduce for the first time coarse corrections for the methods of reflections to make them scalable in the case when the number of particles becomes large. The substructured formulations permit the easy use of the methods of reflections as preconditioners for Krylov methods, and we illustrate scalability and preconditioning properties with numerical experiments.

Published online : 2019-11-29
DOI : https://doi.org/10.5802/smai-jcm.46
Classification:  65N55,  65F10,  65N38,  35J05,  35J57,  35J25
Keywords: Methods of reflections; Domain decomposition methods; Schwarz methods; coarse correction; two-level methods; substructured methods; elliptic PDE; Laplace equation.
@article{SMAI-JCM_2019__5__161_0,
     author = {Gabriele Ciaramella and Martin J. Gander and Laurence Halpern and Julien Salomon},
     title = {Methods of Reflections: relations with Schwarz methods and classical stationary iterations, scalability and preconditioning.},
     journal = {The SMAI journal of computational mathematics},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {5},
     year = {2019},
     pages = {161-193},
     doi = {10.5802/smai-jcm.46},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__5__161_0}
}
Ciaramella, Gabriele; Gander, Martin J.; Halpern, Laurence; Salomon, Julien. Methods of Reflections: relations with Schwarz methods and classical stationary iterations, scalability and preconditioning.. The SMAI journal of computational mathematics, Volume 5 (2019) , pp. 161-193. doi : 10.5802/smai-jcm.46. https://smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__5__161_0/

[1] C. Amrouche; V. Girault; J. Giroire Dirichlet and Neumann exterior problems for the n-dimensional Laplace operator. An approach in weighted Sobolev spaces, J. Math. Pures Appl., Volume 76 (1997) no. 1, pp. 55-81 | Article | MR 1429997 | Zbl 0878.35029

[2] M. Balabane Boundary decomposition for Helmholtz and Maxwell equations 1: disjoint sub-scatterers, Asymptotic Anal., Volume 38 (2004) no. 1, pp. 1-10 | MR 2060617 | Zbl 1099.35023

[3] M. Balabane; V. Tirel Décomposition de domaine pour un calcul hybride de l’équation de Helmholtz, C. R. Acad. Sci. Paris Sér. I Math., Volume 324 (1997) no. 3, pp. 281-286 | Article | Zbl 0879.35010

[4] J. M. Burgers On the influence of the concentration of a suspension upon the sedimentation velocity (in particular for a suspension of spherical particles), Procedings of the Koninklijke Nederlandse Akademie van Wetenshappen, Volume 45 (1942) no. 1/5, pp. 9-16

[5] J. M. Burgers Hydrodynamics. — On the influence of the concentration of a suspension upon the sedimentation velocity (in particular for a suspension of spherical particles), Springer (1995), pp. 452-477

[6] E. Cancès; Y. Maday; B. Stamm Domain decomposition for implicit solvation models, J. Chem. Phys., Volume 139 (2013), 054111 | Article

[7] F. Chaouqui; G. Ciaramella; M. J. Gander; T. Vanzan On the scalability of classical one-level domain-decomposition methods, Vietnam J. Math., Volume 46 (2018) no. 4, pp. 1053-1088 | Article | MR 3878793 | Zbl 1406.65128

[8] G. Ciaramella; M. J. Gander Analysis of the Parallel Schwarz Method for Growing Chains of Fixed-Sized Subdomains: Part I, SIAM J. Numer. Anal., Volume 55 (2017) no. 3, pp. 1330-1356 | Article | MR 3656507 | Zbl 1366.65111

[9] G. Ciaramella; M. J. Gander Analysis of the parallel Schwarz method for growing chains of fixed-sized subdomains: Part II, SIAM J. Numer. Anal., Volume 56 (2018) no. 3, pp. 1498-1524 | Article | MR 3807950 | Zbl 06885719

[10] G. Ciaramella; M. J. Gander Analysis of the parallel Schwarz method for growing chains of fixed-sized subdomains: Part III, Electron. Trans. Numer. Anal., Volume 49 (2018), pp. 201-243 | MR 3874097 | Zbl 1404.65301

[11] G. Ciaramella; M. J. Gander; L. Halpern; J. Salomon Review of the Methods of Reflections, Proceedings Mathematisches Forschungsinstitut Oberwolfach (2017)

[12] J. Coatléven; P. Joly Operator Factorization for Multiple-Scattering Problems and an Application to Periodic Media, Commun. Comput. Phys., Volume 11 (2012) no. 2, pp. 303-318 | Article | MR 2850896 | Zbl 1373.74054

[13] J. Deny; J. L. Lions Les espaces du type de Beppo Levi, Ann. Inst. Fourier, Volume 5 (1954), pp. 305-370 | Article | Zbl 0065.09903

[14] J. K. G. Dhont An introduction to dynamics of colloids, Elsevier, Studies in interface science, Volume 2 (1996)

[15] E. Efstathiou; M. J. Gander Why Restricted Additive Schwarz Converges Faster than Additive Schwarz, BIT Numerical Mathematics, Volume 43 (2003) no. 5, pp. 945-959 | Article | MR 2058877 | Zbl 1045.65027

[16] M. J. Gander Optimized Schwarz Methods, SIAM J. Numer. Anal., Volume 44 (2006) no. 2, pp. 699-731 | Article | MR 2218966 | Zbl 1117.65165

[17] M. J. Gander Schwarz methods over the course of time, Electron. Trans. Numer. Anal., Volume 31 (2008), pp. 228-255 | MR 2569603 | Zbl 1171.65020

[18] M. J. Gander; L. Halpern; K. Santugini Repiquet Discontinuous coarse spaces for DD-methods with discontinuous iterates, Domain Decomposition Methods in Science and Engineering XXI, Springer (2014), pp. 607-615 | Article | Zbl 1382.65439

[19] M. J. Gander; L. Halpern; K. Santugini Repiquet A new coarse grid correction for RAS/AS, Domain Decomposition Methods in Science and Engineering XXI, Springer (2014), pp. 275-283 | Article | Zbl 1382.65438

[20] M. J. Gander; A. Loneland SHEM: An optimal coarse space for RAS and its multiscale approximation, Domain Decomposition Methods in Science and Engineering XXIII, Springer (2017), pp. 313-321 | Article | Zbl 1367.65183

[21] M. J. Gander; A. Loneland; T. Rahman Analysis of a new harmonically enriched multiscale coarse space for domain decomposition methods (2015) (https://arxiv.org/abs/1512.05285)

[22] M. Ganesh; S. C. Hawkins A high-order algorithm for multiple electromagnetic scattering in three dimensions, Numer. Algor., Volume 50 (2009) no. 4, pp. 469-510 | Article | MR 2496648 | Zbl 1175.78011

[23] D. Gilbarg; N. S. Trudinger Elliptic partial differential equations of second order, Springer, Grundlehren der Mathematischen Wissenschaften (1983) | Article | Zbl 0691.35001

[24] G. M. Golusin Auflösung des dreidimensionalen Dirichleteschen Problems für die Laplacesche Gleichung und Gebiete, die durch endlich viele Sphären ohne gemeinsame Punkte begrenzt sind, Mat. Sb., Volume 41 (1934), pp. 277-283 | Zbl 60.0432.03

[25] G. M. Golusin Auflösung einiger ebenen Grundaufaben der mathematischen Physik im Fall der Laplaceschen Gleichung und mehrfachzusammenhängender Gebiete, die durch Kreise begrenzt sind, Mat. Sb., Volume 41 (1934), pp. 246-276 | Zbl 60.0436.01

[26] B. Hanouzet Espaces de Sobolev avec poids. Application au problème de Dirichlet dans un demi espace, Rend. Semin. Mat. Univ. Padova, Volume 46 (1971), pp. 227-272 | Zbl 0247.35041

[27] J. Happel; H. Brenner Low Reynolds number hydrodynamics with special applications to particulate media, Martinus Nijhoff publishers, Mechanics of fluids and transport processes, Volume 1 (1983)

[28] J. Hengstenberg; B. Sturm; O. Winkler Messen und Regeln in der chemischen Technik, Springer (1964) | Article

[29] R. M. Höfer Sedimentation of Inertialess Particles in Stokes Flows, Commun. Math. Phys., Volume 360 (2018) no. 1, pp. 55-101 | Article | MR 3795188 | Zbl 1391.76122

[30] R. M. Höfer; J. J. L. Velázquez The Method of Reflections, Homogenization and Screening for Poisson and Stokes Equations in Perforated Domains, Arch. Ration. Mech. Anal., Volume 227 (2018) no. 3, pp. 1165-1221 | Article | MR 3744384 | Zbl 1384.35089

[31] K. Ichiki; J. F. Brady Many-body effects and matrix inversion in low-Reynolds-number hydrodynamics, Phys. Fluids, Volume 13 (2001) no. 1, pp. 350-353 | Article | Zbl 1184.76241

[32] P. E. Jabin; F. Otto Identification of the dilute regime in particle sedimentation, Commun. Math. Phys., Volume 250 (2004) no. 2, pp. 415-432 | Article | MR 2094523 | Zbl 1059.76073

[33] W. Kahan Gauss-Seidel Methods of Solving Large Systems of Linear Equations, University of Toronto (1958) (Ph. D. Thesis) | MR 2702985

[34] S. Kim; S. J. Karrila Microhydrodynamics: principles and selected applications, Butterworth-Heinemann (1991)

[35] R. Kress Linear Integral Equations, Springer, Applied Mathematical Sciences (2013)

[36] G. J. Kynch The slow motion of two or more spheres through a viscous fluid, J. Fluid Mech., Volume 5 (1959) no. 2, pp. 193-208 | Article | MR 102286 | Zbl 0084.41402

[37] H. Lamb Hydrodynamics (3rd edn), Cambridge University Press (1906)

[38] P. Laurent; G. Legendre; J. Salomon On the method of reflections (2017) (In revision, https://hal.archives-ouvertes.fr/hal-01439871/file/lls_final_hal_v1_2.pdf)

[39] P. L. Lions; R. Glowinski; G. H. Golub; G. A. Meurant; J. Périaux On the Schwarz alternating method. I, First international symposium on domain decomposition methods for partial differential equations, Society for Industrial and Applied Mathematics (1988), pp. 1-42

[40] P. L. Lions; Tony Chan; Roland Glowinski; Jacques Périaux; Olof Widlund On the Schwarz alternating method. II. Stochastic interpretation and other properties, Second International Symposium on Domain Decomposition Methods for Partial Differential Equations, Society for Industrial and Applied Mathematics (1989), pp. 47-70

[41] H. A. Lorentz Abhandlungen über theoretische Physik, BG Teubner (1907) | Zbl 38.0783.01

[42] J. H. C. Luke Convergence of a multiple reflection method for calculating Stokes flow in a suspension, SIAM J. Appl. Math., Volume 49 (1989) no. 6, pp. 1635-1651 | Article | MR 1025951 | Zbl 0682.76087

[43] P. A. Martin Multiple scattering and modified Green’s functions, J. Math. Anal. Appl., Volume 275 (2002) no. 2, pp. 642-656 | Article | MR 1943770 | Zbl 1013.35058

[44] P. A. Martin Multiple Scattering: Interaction of Time-Harmonic Waves with N Obstacles, Cambridge University Press, Encyclopedia of Mathematics and Its Applications (2006) | Zbl 1210.35002

[45] R. Murphy Elementary principles of the theories of electricity, heat, and molecular actions, Printed at the Pitt Press by J. Smith for J. & J. Deighton (1833)

[46] S. Reich; R. Zalas The optimal error bound for the method of simultaneous projections, Journal of Approximation Theory, Volume 223 (2017), pp. 96-107 | Article | MR 3707141 | Zbl 1381.41013

[47] L. F. Richardson The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam, Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, Volume 210 (1911), pp. 307-357 | Zbl 42.0873.02

[48] S. A. Sauter; C. Schwab Boundary Element Methods, Springer, Springer Series in Computational Mathematics (2010)

[49] M. Smoluchowski Über die Wechselwirkung von Kugeln, die sich in einer zähen Flüssigkeit bewegen, Bull. Int. Acad. Sci. Cracovie, Cl. Sci. Math. Nat., Sér. A Sci. Math. (1911), pp. 28-39 | Zbl 42.0815.02

[50] V. Tirel Hybridation par méthode de décomposition de bord appliquée a l’étude des ondes acoustiques et électromagnétiques. Résultats théoriques et numériques, Université Paris 13 (1998) (Ph. D. Thesis)

[51] A. Toselli; O. Widlund Domain Decomposition Methods: Algorithms and Theory, Springer, Springer Series in Computational Mathematics, Volume 34 (2005) | MR 2104179 | Zbl 1069.65138

[52] S. D. Traytak Convergence of a reflection method for diffusion-controlled reactions on static sinks, Phys. A Statist. Mech. Appl., Volume 362 (2006) no. 2, pp. 240-248 | Article

[53] H. Wang; J. Liu On decomposition method for acoustic wave scattering by multiple obstacles, Acta Math. Sci., Volume 33 (2013) no. 1, pp. 1-22 | Article | MR 3003740 | Zbl 1289.74090

[54] D. M. Young Iterative Methods for Solving Partial Difference Equations of Elliptic Type, Harvard University (1950) (Ph. D. Thesis)