Balancing domain decomposition for problems with large jumps in coefficients

Mandel, Jan; Brezina, Marian

doi:10.1090/S0025-5718-96-00757-0

Balancing domain decomposition for problems with large jumps in coefficients
HTML articles powered by AMS MathViewer

by Jan Mandel and Marian Brezina PDF

Math. Comp. 65 (1996), 1387-1401 Request permission

Abstract:

The Balancing Domain Decomposition algorithm uses in each iteration solution of local problems on the subdomains coupled with a coarse problem that is used to propagate the error globally and to guarantee that the possibly singular local problems are consistent. The abstract theory introduced recently by the first-named author is used to develop condition number bounds for conforming linear elements in two and three dimensions. The bounds are independent of arbitrary coefficient jumps between subdomains and of the number of subdomains, and grow only as the squared logarithm of the mesh size $h$. Computational experiments for two- and three-dimensional problems confirm the theory.

References

Steven F. Ashby, Thomas A. Manteuffel, and Paul E. Saylor, A taxonomy for conjugate gradient methods, SIAM J. Numer. Anal. 27 (1990), no. 6, 1542–1568. MR 1080338, DOI 10.1137/0727091
J.-F. Bourgat, Roland Glowinski, Patrick Le Tallec, and Marina Vidrascu, Variational formulation and algorithm for trace operator in domain decomposition calculations, Domain decomposition methods (Los Angeles, CA, 1988) SIAM, Philadelphia, PA, 1989, pp. 3–16. MR 992000
J. H. Bramble, J. E. Pasciak, and A. H. Schatz, The construction of preconditioners for elliptic problems by substructuring. I, Math. Comp. 47 (1986), no. 175, 103–134. MR 842125, DOI 10.1090/S0025-5718-1986-0842125-3
J. H. Bramble, J. E. Pasciak, and A. H. Schatz, An iterative method for elliptic problems on regions partitioned into substructures, Math. Comp. 46 (1986), no. 174, 361–369. MR 829613, DOI 10.1090/S0025-5718-1986-0829613-0
James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz, The construction of preconditioners for elliptic problems by substructuring. IV, Math. Comp. 53 (1989), no. 187, 1–24. MR 970699, DOI 10.1090/S0025-5718-1989-0970699-3
Tony F. Chan, Analysis of preconditioners for domain decomposition, SIAM J. Numer. Anal. 24 (1987), no. 2, 382–390. MR 881372, DOI 10.1137/0724029
Tony F. C. Chan and Tarek P. Mathew, The interface probing technique in domain decomposition, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 212–238. MR 1146663, DOI 10.1137/0613018
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
Lawrence C. Cowsar, Jan Mandel, and Mary F. Wheeler, Balancing domain decomposition for mixed finite elements, Math. Comp. 64 (1995), no. 211, 989–1015. MR 1297465, DOI 10.1090/S0025-5718-1995-1297465-9
Y.-H. De Roeck, Résolution sur Ordinateurs Multi-Processeurs de Problème d’Elasticité par Décomposition de Domaines, PhD thesis, Université Paris IX Daupine, 1991.
Y.-H. De Roeck and P. Le Tallec, Analysis and test of a local domain decomposition preconditioner, in Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations, R. Glowinski, Y. Kuznetsov, G. Meurant, J. Périaux, and O. Widlund, eds., SIAM, Philadelphia, PA, 1991.
M. Dryja, A method of domain decomposition for three-dimensional finite element elliptic problems, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 43–61. MR 972511
Maksymilian Dryja and Olof B. Widlund, Towards a unified theory of domain decomposition algorithms for elliptic problems, Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989) SIAM, Philadelphia, PA, 1990, pp. 3–21. MR 1064335
Maksymilian Dryja and Olof B. Widlund, Additive Schwarz methods for elliptic finite element problems in three dimensions, Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Norfolk, VA, 1991) SIAM, Philadelphia, PA, 1992, pp. 3–18. MR 1189559
Maksymilian Dryja and Olof B. Widlund, Domain decomposition algorithms with small overlap, SIAM J. Sci. Comput. 15 (1994), no. 3, 604–620. Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992). MR 1273155, DOI 10.1137/0915040
—, Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems, Comm. Pure Appl. Math, 48 (1995), pp. 121–155.
Roland Glowinski and Mary Fanett Wheeler, Domain decomposition and mixed finite element methods for elliptic problems, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 144–172. MR 972516
David E. Keyes and William D. Gropp, A comparison of domain decomposition techniques for elliptic partial differential equations and their parallel implementation, SIAM J. Sci. Statist. Comput. 8 (1987), no. 2, S166–S202. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 879402, DOI 10.1137/0908020
Patrick Le Tallec, Jan Mandel, and Marina Vidrascu, Balancing domain decomposition for plates, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 515–524. MR 1312417, DOI 10.1090/conm/180/02014
Jan Mandel, Balancing domain decomposition, Comm. Numer. Methods Engrg. 9 (1993), no. 3, 233–241. MR 1208381, DOI 10.1002/cnm.1640090307
J. Mandel and M. Brezina, Balancing domain decomposition: Theory and computations in two and three dimensions, UCD/CCM Report 2, Center for Computational Mathematics, University of Colorado at Denver, November 1993.
J. Mandel, S. McCormick, and R. Bank, Variational multigrid theory, in Multigrid Methods, S. F. McCormick, ed., SIAM, Philadephia, 1987, ch. 5, pp. 131–177.
M. Sarkis, Two-level Schwarz methods for nonconforming finite elements and discontinuous coefficients, in Proceedings of the Sixth Copper Mountain Conference on Multigrid Methods, Volume 2, N. D. Melson, T. A. Manteuffel, and S. F. McCormick, eds., no. 3224, Hampton VA, 1993, NASA, pp. 543–566.
Scientific Computing Associates, CLAM User’s Guide; The Computational Linear Algebra Machine, Version 2.00, New Haven, CT, 1990.
Barry F. Smith, A domain decomposition algorithm for elliptic problems in three dimensions, Numer. Math. 60 (1991), no. 2, 219–234. MR 1133580, DOI 10.1007/BF01385722
O. B. Widlund, An extension theorem for finite element spaces with three applications, in Numerical Techniques in Continuum Mechanics, W. Hackbusch and K. Witsch, eds., Braunschweig/Wiesbaden, 1987, Notes on Numerical Fluid Mechanics, v. 16, Friedr. Vieweg und Sohn, pp. 110–122. Proceedings of the Second GAMM-Seminar, Kiel, January, 1986.
Olof B. Widlund, Iterative substructuring methods: algorithms and theory for elliptic problems in the plane, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 113–128. MR 972514