Methods of Reflections: relations with Schwarz methods and classical stationary iterations, scalability and preconditioning.

Ciaramella, Gabriele; Gander, Martin J.; Halpern, Laurence; Salomon, Julien

The SMAI Journal of computational mathematics, Tome 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.

Classification : 65N55, 65F10, 65N38, 35J05, 35J57, 35J25
Mots clés : Methods of reflections; Domain decomposition methods; Schwarz methods; coarse correction; two-level methods; substructured methods; elliptic PDE; Laplace equation.

[1] Amrouche, C.; Girault, V.; Giroire, J. 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] Balabane, M. Boundary decomposition for Helmholtz and Maxwell equations 1: disjoint sub-scatterers, Asymptotic Anal., Volume 38 (2004) no. 1, pp. 1-10 | MR | Zbl

[3] Balabane, M.; Tirel, V. 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] Burgers, J. M. 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] Burgers, J. M. 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] Cancès, E.; Maday, Y.; Stamm, B. Domain decomposition for implicit solvation models, J. Chem. Phys., Volume 139 (2013), 054111 | DOI

[7] Chaouqui, F.; Ciaramella, G.; Gander, M. J.; Vanzan, T. 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] Ciaramella, G.; Gander, M. J. 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] Ciaramella, G.; Gander, M. J. 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] Ciaramella, G.; Gander, M. J. 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] Ciaramella, G.; Gander, M. J.; Halpern, L.; Salomon, J. Review of the Methods of Reflections, Proceedings Mathematisches Forschungsinstitut Oberwolfach (2017)

[12] Coatléven, J.; Joly, P. 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] Deny, J.; Lions, J. L. Les espaces du type de Beppo Levi, Ann. Inst. Fourier, Volume 5 (1954), pp. 305-370 | DOI | Zbl

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

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

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

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

[18] Gander, M. J.; Halpern, L.; Repiquet, K. Santugini 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] Gander, M. J.; Halpern, L.; Repiquet, K. Santugini A new coarse grid correction for RAS/AS, Domain Decomposition Methods in Science and Engineering XXI, Springer, 2014, pp. 275-283 | DOI | Zbl

[20] Gander, M. J.; Loneland, A. 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] Gander, M. J.; Loneland, A.; Rahman, T. Analysis of a new harmonically enriched multiscale coarse space for domain decomposition methods (2015) (https://arxiv.org/abs/1512.05285)

[22] Ganesh, M.; Hawkins, S. C. 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] Gilbarg, D.; Trudinger, N. S. Elliptic partial differential equations of second order, Grundlehren der Mathematischen Wissenschaften, Springer, 1983 | DOI | Zbl

[24] Golusin, G. M. 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] Golusin, G. M. 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] Hanouzet, B. 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] Happel, J.; Brenner, H. Low Reynolds number hydrodynamics with special applications to particulate media, Mechanics of fluids and transport processes, 1, Martinus Nijhoff publishers, 1983

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

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

[30] Höfer, R. M.; Velázquez, J. J. L. 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] Ichiki, K.; Brady, J. F. Many-body effects and matrix inversion in low-Reynolds-number hydrodynamics, Phys. Fluids, Volume 13 (2001) no. 1, pp. 350-353 | DOI | Zbl

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

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

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

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

[36] Kynch, G. J. 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] Lamb, H. Hydrodynamics (3rd edn), Cambridge University Press, 1906

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

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

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

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

[42] Luke, J. H. C. 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] Martin, P. A. Multiple scattering and modified Green’s functions, J. Math. Anal. Appl., Volume 275 (2002) no. 2, pp. 642-656 | DOI | MR | Zbl

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

[45] Murphy, R. 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] Reich, S.; Zalas, R. The optimal error bound for the method of simultaneous projections, Journal of Approximation Theory, Volume 223 (2017), pp. 96-107 | DOI | MR | Zbl

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

[49] Smoluchowski, M. Ü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] Tirel, V. 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] Toselli, A.; Widlund, O. Domain Decomposition Methods: Algorithms and Theory, Springer Series in Computational Mathematics, 34, Springer, 2005 | MR | Zbl

[52] Traytak, S. D. 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] Wang, H.; Liu, J. 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] Young, D. M. 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)