Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The convergence
of the cascadic conjugate-gradient method
applied to elliptic problems
in domains with re-entrant corners

Authors: Vladimir Shaidurov and Lutz Tobiska
Journal: Math. Comp. 69 (2000), 501-520
MSC (1991): Primary 65F10; Secondary 65N30
Published electronically: March 18, 1999
MathSciNet review: 1653982
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the convergence properties of the cascadic conjugate-gradient method (CCG-method), which can be considered as a multilevel method without coarse-grid correction. Nevertheless, the CCG-method converges with a rate that is independent of the number of unknowns and the number of grid levels. We prove this property for two-dimensional elliptic second-order Dirichlet problems in a polygonal domain with an interior angle greater than $\pi$. For piecewise linear finite elements we construct special nested triangulations that satisfy the conditions of a ``triangulation of type $(h,\gamma,L)$'' in the sense of I. Babuska, R. B. Kellogg and J. Pitkäranta. In this way we can guarantee both the same order of accuracy in the energy norm of the discrete solution and the same convergence rate of the CCG-method as in the case of quasiuniform triangulations of a convex polygonal domain.

References [Enhancements On Off] (What's this?)

  • 1. I. Babu\v{s}ka, R.B. Kellogg, and J. Pitkäranta, Direct and inverse error estimates for finite elements with mesh refinements, Numer. Math. 33 (1979), 447-471. MR 81c:65054
  • 2. F.A. Bornemann, On the convergence of cascadic iterations for elliptic problems, Tech. Report SC 94-8, Konrad-Zuse-Zentrum Berlin (ZIB), 1994.
  • 3. P. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978. MR 58:25001
  • 4. P. Deuflhard, Cascadic Conjugate Gradient Methods for Elliptic Partial Differential Equations I. Algorithm and Numerical Results, Tech. Report SC 93-23, Konrad-Zuse-Zentrum Berlin (ZIB), 1993.
  • 5. -, Cascadic conjugate gradient methods for elliptic partial differential equations. Algorithm and numerical results, Domain decomposition methods in scientific and engineering computing. Proceedings of the 7th international conference on domain decomposition, October 27-30, 1993, Pennsylvania State University, (D. Keyes and J. Xu, eds.), Contemp. Math., vol. 180, Providence, RI: American Mathematical Society, 1994, pp. 29-42. MR 95i:65008
  • 6. P. Grisvard, Singularities in Boundary Value Problems, Springer-Verlag, Berlin, and Masson, Paris, 1992. MR 93h:35004
  • 7. V.A. Kondrat'ev, Boundary problems for elliptic equations in domains with conical or angular points, Trans. Mosc. Math. Soc. 16 (1967), 227-313. MR 37:1777
  • 8. O.A. Ladyzhenskaya and N.N. Uraltseva, Linear and quasilinear elliptic equations, Academic Press, New York, 1968. MR 39:5941
  • 9. L.A. Oganesjan and L.A. Rukhovets, Variational Difference Methods of Solving the Elliptic Equations (in Russian), Acad. Sci. of the Armenian SSR, Erevan, 1979. MR 92m:65101
  • 10. A.A. Samarskii and E.S. Nikolaev, Numerical Methods for Grid Equations. Vol. II, Iterative Methods, Birkhäuser, Basel, 1989. MR 90m:65003
  • 11. V.V. Shaidurov, The convergence of the cascadic conjugate-gradient method under a deficient regularity, Problems and Methods in Mathematical Physics (L.Jentsch and F.Tröltzsch, eds.), Teubner, Stuttgart, 1994, 185-194. MR 95f:65217
  • 12. -, Some estimates of the rate of convergence for the cascadic conjugate-gradient method, Comput. Math. Appl. 31 (1996), No. 4-5, 161-171. MR 96j:65003
  • 13. -, Multigrid methods for finite elements, Kluwer Academic Publishers, Dordrecht, 1995. MR 97e:65142
  • 14. H. Yserentant, The convergence of multi-level methods for solving finite-element equations in the presence of singularities, Math. Comp. 47 (1986), 399-409. MR 88d:65149

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F10, 65N30

Retrieve articles in all journals with MSC (1991): 65F10, 65N30

Additional Information

Vladimir Shaidurov
Affiliation: Institute of Computational Modelling, Siberian Branch of the Russian Academy of Sciences, Krasnoyarsk 660036, Russia

Lutz Tobiska
Affiliation: Otto-von-Guericke-Universität Magdeburg, Postfach 4120, D-39016 Magdeburg, Germany

Keywords: Multigrid, cascadic algorithm, conjugate-gradient method, finite element method
Received by editor(s): November 11, 1997
Received by editor(s) in revised form: July 10, 1998
Published electronically: March 18, 1999
Additional Notes: The research was supported by the Deutsche Forschungsgemeinschaft.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society