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.

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:
DOI: 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.
Gabriele Ciaramella 1; Martin J. Gander 2; Laurence Halpern 3; Julien Salomon 4

1 University of Konstanz, Germany
2 University of Geneva, Switzerland
3 Université Paris 13, France
4 INRIA Paris, France
License: CC-BY-NC-ND 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@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},
     pages = {161--193},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {5},
     year = {2019},
     doi = {10.5802/smai-jcm.46},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.46/}
}
TY  - JOUR
AU  - Gabriele Ciaramella
AU  - Martin J. Gander
AU  - Laurence Halpern
AU  - Julien Salomon
TI  - Methods of Reflections: relations with Schwarz methods and classical stationary iterations, scalability and preconditioning.
JO  - The SMAI Journal of computational mathematics
PY  - 2019
SP  - 161
EP  - 193
VL  - 5
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.46/
DO  - 10.5802/smai-jcm.46
LA  - en
ID  - SMAI-JCM_2019__5__161_0
ER  - 
%0 Journal Article
%A Gabriele Ciaramella
%A Martin J. Gander
%A Laurence Halpern
%A Julien Salomon
%T Methods of Reflections: relations with Schwarz methods and classical stationary iterations, scalability and preconditioning.
%J The SMAI Journal of computational mathematics
%D 2019
%P 161-193
%V 5
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.46/
%R 10.5802/smai-jcm.46
%G en
%F SMAI-JCM_2019__5__161_0
Gabriele Ciaramella; Martin J. Gander; Laurence Halpern; Julien Salomon. 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/articles/10.5802/smai-jcm.46/

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | DOI | Zbl

[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 | DOI

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

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

[14] J. K. G. Dhont An introduction to dynamics of colloids, Studies in interface science, 2, Elsevier, 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 | DOI | MR | Zbl

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

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

[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 | DOI | Zbl

[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 | DOI | Zbl

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

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

[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

[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

[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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

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

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

[35] R. Kress Linear Integral Equations, Applied Mathematical Sciences, Springer, 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 | DOI | MR | Zbl

[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, First international symposium on domain decomposition methods for partial differential equations (1988), pp. 1-42

[40] P. L. Lions, Second International Symposium on Domain Decomposition Methods for Partial Differential Equations (1989), pp. 47-70

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

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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

[48] S. A. Sauter; C. Schwab Boundary Element Methods, Springer Series in Computational Mathematics, Springer, 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

[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 Series in Computational Mathematics, 34, Springer, 2005 | MR | Zbl

[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 | DOI

[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 | DOI | MR | Zbl

[54] D. M. Young Iterative Methods for Solving Partial Difference Equations of Elliptic Type, Harvard University (1950) (Ph. D. Thesis https://web.ma.utexas.edu/CNA/DMY/david_young_thesis.pdf)

Cited by Sources: