Continuous analysis of the additive Schwarz method: A stable decomposition in $H^1$ with explicit constants

Gander, Martin J.; Halpern, Laurence; Santugini, Kévin

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 3, pp. 713-740.

The classical convergence result for the additive Schwarz preconditioner with coarse grid is based on a stable decomposition. The result holds for discrete versions of the Schwarz preconditioner, and states that the preconditioned operator has a uniformly bounded condition number that depends only on the number of colors of the domain decomposition, the ratio between the average diameter of the subdomains and the overlap width, and on the shape regularity of the domain decomposition. The Schwarz method was however defined at the continuous level, and similarly, the additive Schwarz preconditioner can also be defined at the continuous level. We present in this paper a continuous analysis of the additive Schwarz preconditioned operator with coarse grid in two dimensions. We show that the classical condition number estimate also holds for the continuous formulation, and as in the discrete case, the result is based on a stable decomposition, but now of the Sobolev space $H^1$. The advantage of such a continuous result is that it is independent of the type of fine grid discretization, and thus does the more natural continuous formulation of the Schwarz method justice. The upper bound we provide for the classical condition number is also explicit, which gives us the quantitative dependence of the upper bound on the shape regularity of the domain decomposition.

R.A. Adams and J.F. Fournier, Sobolev Spaces. In vol. 140 of Pure and Appl. Math. Ser., 2dn edn. Academic Press (2003). | MR | Zbl

S.C. Brenner, Lower bounds for two-level additive Schwarz preconditioners with small overlaps. SIAM J. Sci. Comput. 21 (2000) 1657–1669. | DOI | MR | Zbl

X.-C. Cai, An additive Schwarz algorithm for nonselfadjoint elliptic equations. In Proc. of Third International Symposium on Domain Decomposition Methods for Partial Differential Equations. Edited by T. Chan, R. Glowinski, J. Périaux and O. Widlund. SIAM, Philadelphia, PA (1990) 232–244. | MR | Zbl

X.-C. Cai, Additive Schwarz algorithms for parabolic convection-diffusion equations. Numer. Math. 60 (1991) 41–61. | DOI | MR | Zbl

X.-C. Cai, Multiplicative Schwarz methods for parabolic problems. SIAM J. Sci Comput. 15 (1994) 587–603. | DOI | MR | Zbl

X.-C. Cai and O. Widlund, Multiplicative Schwarz algorithms for some nonsymmetric and indefinite problems. SIAM J. Numer. Anal. 30 (1993) 936–952. | DOI | MR | Zbl

C. Canuto and D. Funaro, The Schwarz algorithm for spectral methods. SIAM J. Numer. Anal. 25 (1988) 24–40. | DOI | MR | Zbl

T.F. Chan and T.P. Mathew, Domain decomposition algorithms. In Acta Numerica. Cambridge University Press (1994) 61–143. | MR | Zbl

T.F. Chan, B.F. Smith and J. Zou, Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids. Numer. Math. 73 (1996) 149–167. | DOI | MR | Zbl

T.F. Chan and J. Zou, Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes. Numer. Algorithms 8 (1994) 329–346. | DOI | MR | Zbl

T.F. Chan and J. Zou, A convergence theory of multilevel additive Schwarz methods on unstructured meshes. Numer. Algorithms 13 (1996) 365–398. | DOI | MR | Zbl

L.C. Cowsar, Dual variable Schwarz methods for mixed finite elements. Technical Report TR93-09. Department of Mathematical Sciences, Rice University (1993).

M. Dryja, Additive Schwarz methods for elliptic mortar finite element problems. In Modeling and Optimization of Distributed Parameter Systems with Applications to Engineering. Edited by M.P. Kazimierz Malanowski, Z. Nahorski. IFIP, Chapman & Hall, London (1996) 31–50. | MR | Zbl

M. Dryja and O.B. Widlund, An additive variant of the Schwarz alternating method for the case of many subregions. Technical Report 339, also Ultracomputer Note 131. Department of Computer Science, Courant Institute (1987).

M. Dryja and O.B. Widlund, Domain decomposition algorithms with small overlap. SIAM J. Sci.Comput. 15 (1994) 604–620. | DOI | MR | Zbl

R.E. Ewing and J. Wang, Analysis of the Schwarz algorithm for mixed finite element methods. RAIRO Math. Model. Numer. Anal. 26 (1992) 739–756. | DOI | Numdam | MR | Zbl

X. Feng and O.A. Karakashian, Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems. SIAM J. Numer. Anal. 39 (2002) 1343–1365. | DOI | MR | Zbl

A. Frommer and D.B. Szyld, Weighted max norms, splittings, and overlapping additive Schwarz iterations. Numer. Math. 83 (1999) 259–278. | DOI | MR | Zbl

M.J. Gander, Optimized Schwarz methods. SIAM J. Numer. Anal. 44 (2006) 699–731. | DOI | MR | Zbl

M.J. Gander, Schwarz methods over the course of time. Electron. Trans. Numer. Anal. 31 (2008) 228–255. | MR | Zbl

M.J. Gander, L. Halpern and K. Santugini-Repiquet, Non shape regular domain decompositions: An analysis using a stable decomposition in $H_0^1$. In Domain Decomposition Methods in Science and Engineering XX. Edited by R. Bank, M. Holst, O. Widlund and J. Xu, No. 91. Lect. Notes Comput. Sci. Eng. Springer, Berlin (2013) 485–492. | MR

P. Grisvard, Elliptic problems in nonsmooth domains. Pitman Publishing, Boston (1985). | MR | Zbl

M. Arlindo Casarin Jr, Quasi-optimal Schwarz methods for the conforming spectral element discretization. SIAM J. Numer. Anal. 34 (1997) 2482–2502. | DOI | MR | Zbl

P.-L. Lions, On the Schwarz alternating method. I. In First International Symposium on Domain Decomposition Methods for Partial Differential Equations. Edited by R. Glowinski, G.H. Golub, G.A. Meurant and J. Périaux. Philadelphia, PA (1988) 1–42. SIAM. | MR | Zbl

P.-L. Lions, On the Schwarz alternating method. II. In Domain Decomposition Methods. Edited by T. Chan, R. Glowinski, J. Périaux and O. Widlund. SIAM, Philadelphia, PA (1989) 47–70. | Zbl

P.-L. Lions, On the Schwarz alternating method. III: a variant for nonoverlapping subdomains. In Proc. of Third International Symposium on Domain Decomposition Methods for Partial Differential Equations. Edited by T.F. Chan, R. Glowinski, J. Périaux and O. Widlund, held in Houston, Texas, March 20-22, 1989. SIAM, Philadelphia, PA (1990) 202–223. | MR | Zbl

T.P. Mathew, Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems, part I: Algorithms and numerical results. Numer. Math. 65 (1993) 445–468. | DOI | MR | Zbl

T.P. Mathew, Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems, part II: Theory. Numer. Math. 65 (1993) 469–492. | DOI | MR | Zbl

L.F. Pavarino, Additive Schwarz methods for the p-version finite element method. Numer. Math. 66 (1994) 493–515. | DOI | MR | Zbl

L.F. Pavarino, Schwarz methods with local refinement for the p-version finite element method. Numer. Math. 69 (1994) 185–211. | DOI | MR | Zbl

A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations. Oxford Science Publications (1999). | MR | Zbl

H.A. Schwarz, Über einen Grenzübergang durch alternierendes Verfahren. Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 15 (1870) 272–286. | JFM

B.F. Smith, P.E. Bjørstad and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press (1996). | MR | Zbl

R. Temam, Infinite Dimensional Dynamical Systems, vol. 68, 2nd edition. Appl. Math. Sci. Springer Verlag (1997). | MR | Zbl

A. Toselli and O. Widlund, Domain Decomposition Methods – Algorithms and Theory. In vol. 34 of Springer Ser. Comput. Math. Springer (2004). | MR | Zbl

O.B. Widlund, The development of coarse spaces for domain decomposition algorithms. In Domain Decomposition Methods in Science and Engineering XVIII. Edited by M. Bercovier, M.J. Gander, R. Kornhuber and O. Widlund. In vol. 70 of Lect. Notes Comput. Sci. Eng. (2009) 241–248. | MR | Zbl

J. Xu, Iterative methods by space decomposition and subspace correction. SIAM Reviews 34 (1992) 581–613. | DOI | MR | Zbl