Nonoverlapping domain decomposition methods with a simple coarse space for elliptic problems

Hu, Qiya; Shu, Shi; Wang, Junxian

doi:10.1090/S0025-5718-10-02361-6

Nonoverlapping domain decomposition methods with a simple coarse space for elliptic problems
HTML articles powered by AMS MathViewer

by Qiya Hu, Shi Shu and Junxian Wang PDF

Math. Comp. 79 (2010), 2059-2078 Request permission

Abstract:

We propose a substructuring preconditioner for solving three-dimensional elliptic equations with strongly discontinuous coefficients. The new preconditioner can be viewed as a variant of the classical substructuring preconditioner proposed by Bramble, Pasiack and Schatz (1989), but with much simpler coarse solvers. Though the condition number of the preconditioned system may not have a good bound, we are able to show that the convergence rate of the PCG method with such substructuring preconditioner is nearly optimal, and also robust with respect to the (possibly large) jumps of the coefficient in the elliptic equation.

References

Yves Achdou, Yvon Maday, and Olof B. Widlund, Iterative substructuring preconditioners for mortar element methods in two dimensions, SIAM J. Numer. Anal. 36 (1999), no. 2, 551–580. MR 1675257, DOI 10.1137/S0036142997321005
Owe Axelsson, Iteration number for the conjugate gradient method, Math. Comput. Simulation 61 (2003), no. 3-6, 421–435. MODELLING 2001 (Pilsen). MR 1984142, DOI 10.1016/S0378-4754(02)00097-6
Christoph Börgers, The Neumann-Dirichlet domain decomposition method with inexact solvers on the subdomains, Numer. Math. 55 (1989), no. 2, 123–136. MR 987381, DOI 10.1007/BF01406510
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
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
James H. Bramble, Joseph E. Pasciak, and Apostol T. Vassilev, Analysis of non-overlapping domain decomposition algorithms with inexact solves, Math. Comp. 67 (1998), no. 221, 1–19. MR 1432125, DOI 10.1090/S0025-5718-98-00879-5
James H. Bramble and Jinchao Xu, Some estimates for a weighted $L^2$ projection, Math. Comp. 56 (1991), no. 194, 463–476. MR 1066830, DOI 10.1090/S0025-5718-1991-1066830-3
Maksymilian Dryja, Barry F. Smith, and Olof B. Widlund, Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions, SIAM J. Numer. Anal. 31 (1994), no. 6, 1662–1694. MR 1302680, DOI 10.1137/0731086
Maksymilian Dryja and Olof B. Widlund, Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems, Comm. Pure Appl. Math. 48 (1995), no. 2, 121–155. MR 1319698, DOI 10.1002/cpa.3160480203
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
Charbel Farhat, Jan Mandel, and François-Xavier Roux, Optimal convergence properties of the FETI domain decomposition method, Comput. Methods Appl. Mech. Engrg. 115 (1994), no. 3-4, 365–385. MR 1285024, DOI 10.1016/0045-7825(94)90068-X
G. Haase, U. Langer, and A. Meyer, The approximate Dirichlet domain decomposition method. II. Applications to 2nd-order elliptic BVPs, Computing 47 (1991), no. 2, 153–167 (English, with German summary). MR 1139434, DOI 10.1007/BF02253432
Qiya Hu and Guoping Liang, Acceleration of the non-symmetrized two-level iteration, Appl. Numer. Math. 41 (2002), no. 2, 305–323. MR 1897012, DOI 10.1016/S0168-9274(01)00102-7
Qiya Hu, Zhongci Shi, and Dehao Yu, Efficient solvers for saddle-point problems arising from domain decompositions with Lagrange multipliers, SIAM J. Numer. Anal. 42 (2004), no. 3, 905–933. MR 2112786, DOI 10.1137/S0036142902404108
Qiya Hu and Jun Zou, A nonoverlapping domain decomposition method for Maxwell’s equations in three dimensions, SIAM J. Numer. Anal. 41 (2003), no. 5, 1682–1708. MR 2035002, DOI 10.1137/S0036142901396909
Qiya Hu and Jun Zou, Substructuring preconditioners for saddle-point problems arising from Maxwell’s equations in three dimensions, Math. Comp. 73 (2004), no. 245, 35–61. MR 2034110, DOI 10.1090/S0025-5718-03-01541-2
Axel Klawonn, Olof B. Widlund, and Maksymilian Dryja, Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients, SIAM J. Numer. Anal. 40 (2002), no. 1, 159–179. MR 1921914, DOI 10.1137/S0036142901388081
Yu. A. Kuznetsov, Efficient iterative solvers for elliptic finite element problems on nonmatching grids, Russian J. Numer. Anal. Math. Modelling 10 (1995), no. 3, 187–211. MR 1343473, DOI 10.1515/rnam.1995.10.3.187
U. Langer and O. Steinbach, Boundary element tearing and interconnecting methods, Computing 71 (2003), no. 3, 205–228. MR 2023942, DOI 10.1007/s00607-003-0018-2
Jan Mandel and Marian Brezina, Balancing domain decomposition for problems with large jumps in coefficients, Math. Comp. 65 (1996), no. 216, 1387–1401. MR 1351204, DOI 10.1090/S0025-5718-96-00757-0
Jan Mandel and Radek Tezaur, On the convergence of a dual-primal substructuring method, Numer. Math. 88 (2001), no. 3, 543–558. MR 1835470, DOI 10.1007/s211-001-8014-1
Barry F. Smith, Petter E. Bjørstad, and William D. Gropp, Domain decomposition, Cambridge University Press, Cambridge, 1996. Parallel multilevel methods for elliptic partial differential equations. MR 1410757
Patrick Le Tallec, Domain decomposition methods in computational mechanics, Comput. Mech. Adv. 1 (1994), no. 2, 121–220. MR 1263805
Charles H. Tong, Tony F. Chan, and C.-C. Jay Kuo, A domain decomposition preconditioner based on a change to a multilevel nodal basis, SIAM J. Sci. Statist. Comput. 12 (1991), no. 6, 1486–1495. MR 1129659, DOI 10.1137/0912082
A. Toselli, Dual-primal FETI algorithms for edge element approximations: three-dimensional h finite elements on shape-regular meshes, to appear in IMA J. Numer. Anal.
Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
Andrea Toselli, Olof B. Widlund, and Barbara I. Wohlmuth, An iterative substructuring method for Maxwell’s equations in two dimensions, Math. Comp. 70 (2001), no. 235, 935–949. MR 1710632, DOI 10.1090/S0025-5718-00-01244-8
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
Jinchao Xu and Yunrong Zhu, Uniform convergent multigrid methods for elliptic problems with strongly discontinuous coefficients, Math. Models Methods Appl. Sci. 18 (2008), no. 1, 77–105. MR 2378084, DOI 10.1142/S0218202508002619
J. Xu and J. Zou, Some non-overlapping domain decomposition methods, SIAM Review, 24(1998)