×

Convergence rate estimate for a domain decomposition method. (English) Zbl 0727.65105

We provide a convergence rate analysis for a variant of the domain decomposition method introduced by the second and the third author for solving the algebraic equations that arise from finite element discretization of nonsymmetric and indefinite elliptic problems with Dirichlet boundary conditions in \({\mathbb{R}}^ 2\). We show that the convergence rate of the preconditioned GMRES method is nearly optimal in the sense that the rate of convergence depends only logarithmically on the mesh size and the number of substructures, if the global coarse mesh is fine enough.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
35J25 Boundary value problems for second-order elliptic equations
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Bank, R.E., Yeserentant, H. (1989): Some Remarks on the Hierarchical Basis Multigrid Method. In: T. Chan, R. Glowinski, J. Périaux, O. Widlund, eds., Domain Decomposition Methods. SIAM
[2] Bramble, J.H., Pasciak, J.E., Schatz, A.H. (1986): The Construction of Preconditioners for Elliptic Problems by Substructuring. Math. Comput.47, 103-134 · Zbl 0615.65112
[3] Bramble, J.H., Pasciak, J.E., Xu, J.C. (1988): The Analysis of Multigrid Algorithms for Nonsymmetric and Indefinite Elliptic Problems. Math. Comput.51, 389-414 · Zbl 0699.65075
[4] Cai, X.-C. (1989): Some Domain Decomposition Algorithms for Nonselfadjoint Elliptic and Parabolic Partial Differential Equations. Ph.D. thesis, Courant Institute, New York University
[5] Cai, X.-C. (1990): An Additive Schwarz Algorithm for Nonselfadjoint Elliptic Equations. In: T. Chan, R. Glowinski, J. Périaux, O. Widlund, eds., Third International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, PA · Zbl 0701.65072
[6] Cai, X.-C., Widlund, O.B. (1992): Domain Decomposition Algorithms for Indefinite Elliptic Problems. SIAM J. Sci Stat. Comput.13 · Zbl 0746.65085
[7] Cai, X.-C., Gropp, W.D., Keyes, D.E. (1991): A Comparisons of Some Domain Decomposition Algorithms for Nonsymmetric Elliptic Problems. In: T. Chan, D. Keyes, G. Meurant, J. Scroggs, R. Voigt, eds., Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, PA
[8] Chan, T.F., Keyes, D.E., (1990): Interface Preconditionings for Domain-Decomposed Convection-Diffusion Operators. In: T. Chan, R. Glowinski, J. Périaux, O. Widlund, eds., Third International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA · Zbl 0722.65060
[9] Dryja, M. (1982): A Capacitance Matrix Method for Dirichlet Problem on Polygonal Region. Numer, Math.39, 51-64 · Zbl 0478.65062
[10] Dryja, M., Widlund, O.B. (1989): Some Domain Decomposition Algorithms for Elliptic Problems. In: Proceedings of the Conference on Iterative Methods for Large Linear Systems. Academic Press, Orlando, Florida · Zbl 0668.65084
[11] Dryja, M., Widlund, O.B. (1990): Towards a Unified Theory of Domain Decomposition Algorithms for Elliptic Problems. In: T. Chan, R. Glowinski, J. Périaux, O. Widlund, eds., Third Internationals Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, PA · Zbl 0719.65084
[12] Eisenstat, S.C., Elman, H.C., Schultz, M.H. (1983): Variational Iterative Methods for Non-symmetric System of Linear Equations. SIAM J. Numer. Anal.20, 345-357 · Zbl 0524.65019
[13] Gropp, W.D., Keyes, D.E. (1991): Domain Decomposition with Local Mesh Refinement. ICASE Report 91-19; SIAM J. Sci. Stat. Comput. (accepted)
[14] Gropp, W.D., Keyes, D.E. (1992): Parallel Performance of Domain-Decomposed Preconditioned Krylov Methods for PDEs with Locally Uniform Refinement. Research Report YALEU/DCS/RR-773; SIAM J. Sci. Stat. Comput.3 · Zbl 0752.65083
[15] Mandel, J., McCormick, S., Bank, R. (1987): Variational Multigrid Theory. In: S. McCormick, eds., Multigrid Methods. SIAM, Philadelphia, PA
[16] Ne?as, J. (1964): Sur la coercivité des formes sesquilinéaires. Rev. Roumaine Math. Pures Appl.9, 47-69 · Zbl 0196.40701
[17] Saad, Y., Schultz, M.H. (1986): GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems. SIAM J. Sci. Stat. Comput.7, 865-869 · Zbl 0599.65018
[18] Schatz, A.H. (1974): An Observation Concerning Ritz-Galerkin Methods with Indefinite Bilinear Forms. Math. Comput28, 959-962 · Zbl 0321.65059
[19] Widlund, O.B. (1988): Iterative Substructuring Methods: Algorithms and Theory for Elliptic Problems in the Plane. In: R. Glowinski, G.H. Golub, G.A. Meurant, J. Périaux, eds., Domain Decomposition Methods of Partial Differential Equations. SIAM, Philadelphia, PA · Zbl 0662.65097
[20] Xu, J. (1989): Theory of Multilevel Methods. Ph.D thesis, Cornell University
[21] Xu, J., Cai, X.-C. (1992): A Preconditioned GMRES Method for Nonsymmetric or Indefinite Problems. Math. Comput. (accepted) · Zbl 0766.65034
[22] Yserentant, H. (1986): On the Multi-level Splitting of Finite Element Spaces for Indefinite Elliptic Boundary Value Problems. SIAM J. Numer. Anal.23, 581-595 · Zbl 0616.65102
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.