New estimates for multilevel algorithms including the $V$-cycle
HTML articles powered by AMS MathViewer
- by James H. Bramble and Joseph E. Pasciak PDF
- Math. Comp. 60 (1993), 447-471 Request permission
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
- Ivo Babuška and A. K. Aziz, Survey lectures on the mathematical foundations of the finite element method, The mathematical foundations of the finite element method with applications to partial differential equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972) Academic Press, New York, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR 0421106
- Randolph E. Bank and Todd Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), no. 153, 35–51. MR 595040, DOI 10.1090/S0025-5718-1981-0595040-2
- D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the $V$-cycle, SIAM J. Numer. Anal. 20 (1983), no. 5, 967–975. MR 714691, DOI 10.1137/0720066 J. H. Bramble, Z. Leyk, and J. E. Pasciak, The analysis of multigrid algorithms for pseudo-differential operators of order minus one, preprint. —, Iterative schemes for non-symmetric and indefinite elliptic boundary value problems, BNL Rep. 45870.
- James H. Bramble and Joseph E. Pasciak, The analysis of smoothers for multigrid algorithms, Math. Comp. 58 (1992), no. 198, 467–488. MR 1122058, DOI 10.1090/S0025-5718-1992-1122058-0
- James H. Bramble and Joseph E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), no. 180, 311–329. MR 906174, DOI 10.1090/S0025-5718-1987-0906174-X
- 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, DOI 10.1090/S0025-5718-1991-1090464-8
- James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comp. 57 (1991), no. 195, 23–45. MR 1079008, DOI 10.1090/S0025-5718-1991-1079008-4 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.
- James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms, Math. Comp. 56 (1991), no. 193, 1–34. MR 1052086, DOI 10.1090/S0025-5718-1991-1052086-4
- James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
- Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
- Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
- Monique Dauge, Elliptic boundary value problems on corner domains, Lecture Notes in Mathematics, vol. 1341, Springer-Verlag, Berlin, 1988. Smoothness and asymptotics of solutions. MR 961439, DOI 10.1007/BFb0086682
- Naomi H. Decker, Jan Mandel, and Seymour V. Parter, On the role of regularity in multigrid methods, Multigrid methods (Copper Mountain, CO, 1987) Lecture Notes in Pure and Appl. Math., vol. 110, Dekker, New York, 1988, pp. 143–156. MR 959341 P. Grisvard, Elliptic problems in non smooth domains, Pitman, Boston, 1985. W. Hackbusch, Multi-grid methods and applications, Springer-Verlag, New York, 1985.
- J.-L. Lions and E. Magenes, Problèmes aux limites non homogènes et applications. Vol. 1, Travaux et Recherches Mathématiques, No. 17, Dunod, Paris, 1968 (French). MR 0247243
- 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 (Bristol, 1983) Inst. Math. Appl. Conf. Ser. New Ser., vol. 3, Oxford Univ. Press, New York, 1985, pp. 213–223. MR 849375
- J. Mandel, S. McCormick, and R. Bank, Variational multigrid theory, Multigrid methods, Frontiers Appl. Math., vol. 3, SIAM, Philadelphia, PA, 1987, pp. 131–177. MR 972757 P. Oswald, On discrete norm estimates related to multilevel preconditioners in the finite element method, preprint. X. Zhang, Multi-level additive Schwarz methods, Courant Inst. Math. Sci., Dept. Comp. Sci. Rep. (August, 1991).
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 60 (1993), 447-471
- MSC: Primary 65N55; Secondary 65N12
- DOI: https://doi.org/10.1090/S0025-5718-1993-1176705-9
- MathSciNet review: 1176705