Analysis of non-overlapping domain decomposition algorithms with inexact solves. (English) Zbl 0902.65067
The authors construct and analyze new non-overlapping domain decomposition preconditioners with inexact solves which can be applied to second-order elliptic and parabolic boundary value problems. In particular, they show that the non-overlapping preconditioners are of additive Schwarz type. These preconditioners exhibit the same asymptotic condition number growth as the corresponding preconditioners with exact subdomain solves and they are much more efficient computationally: this is numerically illustrated on several example.
Reviewer: M.Bernadou (Le Chesnay)
MSC:
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |
| 35K15 | Initial value problems for second-order parabolic equations |
| 65F10 | Iterative numerical methods for linear systems |
| 35J25 | Boundary value problems for second-order elliptic equations |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65M60 | Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
Keywords:
preconditioning; numerical examples; second-order elliptic equations; second-order parabolic equations; non-overlapping domain decomposition; inexact solves; condition numberReferences:
| [1] | Petter E. Bjørstad and Olof B. Widlund, Iterative methods for the solution of elliptic problems on regions partitioned into substructures, SIAM J. Numer. Anal. 23 (1986), no. 6, 1097 – 1120. · Zbl 0615.65113 · doi:10.1137/0723075 |
| [2] | Christoph Börgers, The Neumann-Dirichlet domain decomposition method with inexact solvers on the subdomains, Numer. Math. 55 (1989), no. 2, 123 – 136. · Zbl 0652.65080 · doi:10.1007/BF01406510 |
| [3] | J. H. Bramble, C. I. Goldstein, and J. E. Pasciak, Analysis of \?-cycle multigrid algorithms for forms defined by numerical quadrature, SIAM J. Sci. Comput. 15 (1994), no. 3, 566 – 576. Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992). · Zbl 0802.65121 · doi:10.1137/0915037 |
| [4] | 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. · Zbl 0595.65111 |
| [5] | 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. · Zbl 0615.65112 |
| [6] | J. H. Bramble, J. E. Pasciak, and A. H. Schatz, The construction of preconditioners for elliptic problems by substructuring. II, Math. Comp. 49 (1987), no. 179, 1 – 16. · Zbl 0623.65118 |
| [7] | James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz, The construction of preconditioners for elliptic problems by substructuring. III, Math. Comp. 51 (1988), no. 184, 415 – 430. · Zbl 0701.65070 |
| [8] | 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. · Zbl 0668.65082 |
| [9] | James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp. 57 (1991), no. 195, 1 – 21. · Zbl 0754.65085 |
| [10] | James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1 – 22. · Zbl 0703.65076 |
| [11] | J.H. Bramble, J.E. Pasciak and J. Xu, A multilevel preconditioner for domain decomposition boundary systems, Proceedings of the 10’th Inter. Conf. on Comput. Meth. in Appl. Sci. and Engr., Nova Sciences, New York, 1992. |
| [12] | James H. Bramble and Jinchao Xu, Some estimates for a weighted \?² projection, Math. Comp. 56 (1991), no. 194, 463 – 476. · Zbl 0722.65057 |
| [13] | Lawrence C. Cowsar, Jan Mandel, and Mary F. Wheeler, Balancing domain decomposition for mixed finite elements, Math. Comp. 64 (1995), no. 211, 989 – 1015. · Zbl 0828.65135 |
| [14] | M. Dryja, A capacitance matrix method for Dirichlet problem on polygon region, Numer. Math. 39 (1982), no. 1, 51 – 64. · Zbl 0478.65062 · doi:10.1007/BF01399311 |
| [15] | 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. · Zbl 0661.65106 |
| [16] | 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. · Zbl 0818.65114 · doi:10.1137/0731086 |
| [17] | 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). · Zbl 0802.65119 · doi:10.1137/0915040 |
| [18] | Ruth Gonzalez and Mary Fanett Wheeler, Domain decomposition for elliptic partial differential equations with Neumann boundary conditions, Proceedings of the international conference on vector and parallel computing — issues in applied research and development (Loen, 1986), 1987, pp. 257 – 263. · Zbl 0652.65079 · doi:10.1016/0167-8191(87)90022-6 |
| [19] | G. Haase, U. Langer, and A. Meyer, The approximate Dirichlet domain decomposition method. I. An algebraic approach, Computing 47 (1991), no. 2, 137 – 151 (English, with German summary). , https://doi.org/10.1007/BF02253431 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). · Zbl 0741.65092 · doi:10.1007/BF02253432 |
| [20] | S.V. Nepomnyaschikh, Application of domain decomposition to elliptic problems with discontinuous coefficients, Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations, (eds, R. Glowinski, Y.A. Kuznetzov, G.A. Meurant, and J. Périaux) SIAM, Phil. PN, 1991, pp. 242-251. CMP 91:12 · Zbl 0766.65106 |
| [21] | B.F. Smith, Domain Decomposition Algorithms for the Partial Differential Equations of Linear Elasticity, Ph.D. Thesis, Courant Institute of Mathematical Sciences, Dept. of Computer Science Tech. Rep. 517, New York, 1990. |
| [22] | A.T. Vassilev, On Discretization and Iterative Techniques for Second-Order Problems with Applications to Multiphase Flow in Porous Media, Ph.D. Thesis, Texas A&M University, College Station, Texas, 1996. |
| [23] | 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. · Zbl 0662.65097 |
| [24] | Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581 – 613. · Zbl 0788.65037 · doi:10.1137/1034116 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
