Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



New estimates for multilevel algorithms including the $ V$-cycle

Authors: James H. Bramble and Joseph E. Pasciak
Journal: Math. Comp. 60 (1993), 447-471
MSC: Primary 65N55; Secondary 65N12
MathSciNet review: 1176705
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The purpose of this paper is to provide new estimates for certain multilevel algorithms. In particular, we are concerned with the simple additive multilevel algorithm discussed recently together with J. Xu and the standard V-cycle algorithm with one smoothing step per grid. We shall prove that these algorithms have a uniform reduction per iteration independent of the mesh sizes and number of levels, even on nonconvex domains which do not provide full elliptic regularity. For example, the theory applies to the standard multigrid V-cycle on the L-shaped domain, or a domain with a crack, and yields a uniform convergence rate. We also prove uniform convergence rates for the multigrid V-cycle for problems with nonuniformly refined meshes. Finally, we give a new multigrid approach for problems on domains with curved boundaries and prove a uniform rate of convergence for the corresponding multigrid V-cycle algorithms.

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

  • [1] A. K. Aziz and I. Babuška, Survey lectures on the mathematical foundations of the finite element method, Part I, The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations (A. K. Aziz, ed.), Academic Press, New York, 1972, pp. 1-362. MR 0421106 (54:9111)
  • [2] R. E. Bank and T. Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), 35-51. MR 595040 (82b:65113)
  • [3] D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the V-cycle, SIAM J. Numer. Anal. 20 (1983), 967-975. MR 714691 (85h:65233)
  • [4] J. H. Bramble, Z. Leyk, and J. E. Pasciak, The analysis of multigrid algorithms for pseudo-differential operators of order minus one, preprint.
  • [5] -, Iterative schemes for non-symmetric and indefinite elliptic boundary value problems, BNL Rep. 45870.
  • [6] J. H. Bramble and J. E. Pasciak, The analysis of smoothers for multigrid algorithms, Math. Comp. 58 (1992), 467-488. MR 1122058 (92f:65146)
  • [7] -, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), 311-329. MR 906174 (89b:65234)
  • [8] 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), 1-21. MR 1090464 (92d:65094)
  • [9] -, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comp. 57 (1991), 23-45. MR 1079008 (91m:65158)
  • [10] J. H. Bramble, J. E. Pasciak and J. Xu, A multilevel preconditioner for domain decomposition boundary systems, Proceedings of the 10th Internat. Conf. on Comput. Methods. in Appl. Sci. and Engr., Nova Sciences, New York, 1992.
  • [11] -, The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms, Math. Comp. 56 (1991), 1-34. MR 1052086 (91h:65159)
  • [12] -, Parallel multilevel preconditioners, Math. Comp. 55 (1990), 1-22. MR 1023042 (90k:65170)
  • [13] A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), 333-390. MR 0431719 (55:4714)
  • [14] P. G. Ciarlet, The finite element method for elliptic problems, North-Holland, New York, 1978. MR 0520174 (58:25001)
  • [15] M. Dauge, Elliptic boundary value problems on corner domains, Lecture Notes in Math., vol. 1341, Springer-Verlag, Berlin and New York,, 1988. MR 961439 (91a:35078)
  • [16] N. H. Decker, S. V. Parter, and J. Mandel, On the role of regularity in multigrid methods, Multigrid Methods, Proceedings of the Third Copper Mountain Conference (S. McCormick, ed.), Marcel Dekker, New York, 1988, pp. 143-156. MR 959341 (90h:65167)
  • [17] P. Grisvard, Elliptic problems in non smooth domains, Pitman, Boston, 1985.
  • [18] W. Hackbusch, Multi-grid methods and applications, Springer-Verlag, New York, 1985.
  • [19] J. L. Lions and E. Magenes, Problèmes aux limites non homogènes et applications, vol. 1, Dunod, Paris, 1968. MR 0247243 (40:512)
  • [20] J.-F. Maitre and F. Musy, Algebraic formalisation of the multigrid method in the symmetric and positive definite case--a convergence estimation for the V-cycle, Multigrid Methods for Integral and Differential Equations (D. J. Paddon and H. Holstien, eds), Clarendon Press, Oxford, 1985, pp. 213-223. MR 849375 (87i:65044)
  • [21] J. Mandel, S. McCormick, and R. Bank, Variational multigrid theory, Multigrid Methods, (S. McCormick, ed.), SIAM, Philadelphia, PA, 1987, pp. 131-178. MR 972757
  • [22] P. Oswald, On discrete norm estimates related to multilevel preconditioners in the finite element method, preprint.
  • [23] X. Zhang, Multi-level additive Schwarz methods, Courant Inst. Math. Sci., Dept. Comp. Sci. Rep. (August, 1991).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65N55, 65N12

Retrieve articles in all journals with MSC: 65N55, 65N12

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society