Analysis of nonoverlapping domain decomposition algorithms with inexact solves
Authors:
James H. Bramble, Joseph E. Pasciak and Apostol T. Vassilev
Journal:
Math. Comp. 67 (1998), 119
MSC (1991):
Primary 65N30, 65F10
MathSciNet review:
1432125
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper we construct and analyze new nonoverlapping domain decomposition preconditioners for the solution of secondorder elliptic and parabolic boundary value problems. The preconditioners are developed using uniform preconditioners on the subdomains instead of exact solves. They exhibit the same asymptotic condition number growth as the corresponding preconditioners with exact subdomain solves and are much more efficient computationally. Moreover, this asymptotic condition number growth is bounded independently of jumps in the operator coefficients across subdomain boundaries. We also show that our preconditioners fit into the additive Schwarz framework with appropriately chosen subspace decompositions. Condition numbers associated with the new algorithms are computed numerically in several cases and compared with those of the corresponding algorithms in which exact subdomain solves are used.
 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. MR 865945
(88h:65188), http://dx.doi.org/10.1137/0723075
 2.
Christoph
Börgers, The NeumannDirichlet domain decomposition method
with inexact solvers on the subdomains, Numer. Math.
55 (1989), no. 2, 123–136. MR 987381
(90f:65191), http://dx.doi.org/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). MR 1273152
(95b:65047), http://dx.doi.org/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. MR 829613
(88a:65123), http://dx.doi.org/10.1090/S00255718198608296130
 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. MR 842125
(87m:65174), http://dx.doi.org/10.1090/S00255718198608421253
 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. MR 890250
(88j:65248), http://dx.doi.org/10.1090/S00255718198708902504
 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. MR 935071
(89e:65118), http://dx.doi.org/10.1090/S0025571819880935071X
 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. MR 970699
(89m:65098), http://dx.doi.org/10.1090/S00255718198909706993
 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. MR 1090464
(92d:65094), http://dx.doi.org/10.1090/S00255718199110904648
 10.
James
H. Bramble, Joseph
E. Pasciak, and Jinchao
Xu, Parallel multilevel
preconditioners, Math. Comp.
55 (1990), no. 191, 1–22. MR 1023042
(90k:65170), http://dx.doi.org/10.1090/S00255718199010230426
 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. MR 1066830
(91k:65140), http://dx.doi.org/10.1090/S00255718199110668303
 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. MR 1297465
(95j:65161), http://dx.doi.org/10.1090/S00255718199512974659
 14.
M.
Dryja, A capacitance matrix method for Dirichlet problem on polygon
region, Numer. Math. 39 (1982), no. 1,
51–64. MR
664536 (83g:65102), http://dx.doi.org/10.1007/BF01399311
 15.
M.
Dryja, A method of domain decomposition for threedimensional
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
(90b:65200)
 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. MR 1302680
(95m:65211), http://dx.doi.org/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). MR 1273155
(95d:65102), http://dx.doi.org/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. MR 898046
(88d:65148), http://dx.doi.org/10.1016/01678191(87)900226
 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). MR 1139433
(93e:65146a), http://dx.doi.org/10.1007/BF02253431
 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. 242251. CMP 91:12
 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 SecondOrder 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. MR 972514
(90c:65138)
 24.
Jinchao
Xu, Iterative methods by space decomposition and subspace
correction, SIAM Rev. 34 (1992), no. 4,
581–613. MR 1193013
(93k:65029), http://dx.doi.org/10.1137/1034116
 1.
 P.E. Bjørstad and O.B. Widlund, Iterative methods for the solution of elliptic problems on regions partitioned into substructures, SIAM J. Numer. Anal. 23 (1986), 10971120. MR 88h:65188
 2.
 C. Börgers, The NeumannDirichlet Domain Decomposition Method with Inexact Solvers on the Subdomains, Numerische Mathematik 55 (1989), 123136. MR 90f:65191
 3.
 J.H. Bramble, C.I. Goldstein, and J.E. Pasciak, Analysis of Vcycle multigrid algorithms for forms defined by numerical quadrature, SIAM Sci. Stat. Comp. 15 (1994), 566576. MR 95b:65047
 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), 361369. MR 88a:65123
 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), 103134. MR 87m:65174
 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), 116. MR 88j:65248
 7.
 J.H. Bramble, J.E. Pasciak and A.H. Schatz , The construction of preconditioners for elliptic problems by substructuring, III, Math. Comp. 51 (1988), 415430. MR 89e:65118
 8.
 J.H. Bramble, J.E. Pasciak and A.H. Schatz , The construction of preconditioners for elliptic problems by substructuring, IV, Math. Comp. 53 (1989), 124. MR 89m:65098
 9.
 J.H. Bramble, J.E. Pasciak, J. Wang, and J. Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp. 57 (1991), 121. MR 92d:65094
 10.
 J.H. Bramble, J.E. Pasciak and J. Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), 122. MR 90k:65170
 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.
 J.H. Bramble and J. Xu, Some estimates for weighted projections, Math. Comp. 56 (1991), 463476. MR 91k:65140
 13.
 L.C. Cowsar, J. Mandel, and M.F. Wheeler, Balancing Domain Decomposition for Mixed Finite Elements, Math. Comp. 64 (1995), 9891015. MR 95j:65161
 14.
 M. Dryja, A capacitance matrix method for the Dirichlet problem on a polygonal region, Numer. Math. 39 (1982), 5164. MR 83g:65102
 15.
 M. Dryja, A method of domain decomposition for threedimensional finite element elliptic problems, First International Symposium on Domain Decomposition Methods for Partial Differential Equations, (eds, R. Glowinski, G.H. Golub, G.A. Meurant, and J. Périaux) SIAM, Phil. PN, 1988, pp. 4361. MR 90b:65200
 16.
 M. Dryja, B.F. Smith, and O.B. Widlund, Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions, SIAM J. Num. Anal. 31 (1994), 16621694. MR 95m:65211
 17.
 M. Dryja and O.B. Widlund, Domain decomposition algorithms with small overlap, SIAM J. Sci. Comput. 15 (1994), 604620. MR 95d:65102
 18.
 R. Gonzalez and M.F. Wheeler, Domain decomposition for elliptic partial differential equations with Neumann boundary conditions., Proceedings, International conference on vector and parallel computingissues in applied research and development, Loen, 1986., vol. 5, Parallel Comput., 1987, pp. 257263. MR 88d:65148
 19.
 G. Haase, U. Langer, and A. Meyer, The Approximate Dirichlet Domain Decomposition Method. Part I: An Algebraic Approach, Computing 47 (1991), 137151. MR 93e:65146a
 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. 242251. CMP 91:12
 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 SecondOrder Problems with Applications to Multiphase Flow in Porous Media, Ph.D. Thesis, Texas A&M University, College Station, Texas, 1996.
 23.
 O. Widlund, Iterative substructuring methods: algorithms and theory for elliptic problems in the plane, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (R. Glowinski, G.H. Golub, G.A. Meurant, and J. Périaux, eds.), SIAM, Phil. PN, 1988, pp. 113128. MR 90c:65138
 24.
 J. Xu, Iterative methods by space decomposition and subspace correction, vol. 34, SIAM Review, 1992, pp. 581613. MR 93k:65029
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
65N30,
65F10
Retrieve articles in all journals
with MSC (1991):
65N30,
65F10
Additional Information
James H. Bramble
Affiliation:
Department of Mathematics, Texas A&M University, College Station, Texas 77843
Email:
bramble@math.tamu.edu
Joseph E. Pasciak
Affiliation:
Department of Mathematics, Texas A&M University, College Station, Texas 77843
Email:
pasciak@math.tamu.edu
Apostol T. Vassilev
Affiliation:
Schlumberger, 8311 N. FM 620 Rd., Austin, Texas 78726
Email:
vassilev@slb.com
DOI:
http://dx.doi.org/10.1090/S0025571898008795
PII:
S 00255718(98)008795
Received by editor(s):
February 21, 1996
Received by editor(s) in revised form:
September 6, 1996
Additional Notes:
This manuscript has been authored under contract number DEAC0276CH00016 with the U.S. Department of Energy. Accordingly, the U.S. Government retains a nonexclusive, royaltyfree license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes. This work was also supported in part under the National Science Foundation Grant No. DMS9007185 and by the PICS ground water research initiative under contract AS413ASD.
Article copyright:
© Copyright 1998
American Mathematical Society
