Optimal-order nonnested multigrid methods for solving finite element equations. I. On quasi-uniform meshes
HTML articles powered by AMS MathViewer
- by Shangyou Zhang PDF
- Math. Comp. 55 (1990), 23-36 Request permission
Abstract:
We prove that the multigrid method works with optimal computational order even when the multiple meshes are not nested. When a coarse mesh is not a submesh of the finer one, the coarse-level correction usually does not have the $a( \cdot , \cdot )$ projection property and does amplify the iterative error in some components. Nevertheless, the low-frequency components of the error can still be caught by the coarse-level correction. Since the (amplified) high-frequency errors will be damped out by the fine-level smoothing efficiently, the optimal work order of the standard multigrid method can still be maintained. However, unlike the case of nested meshes, a nonnested multigrid method with one smoothing does not converge in general, no matter whether it is a V-cycle or a W-cycle method. It is shown numerically that the convergence rates of nonnested multigrid methods are not necessarily worse than those of nested ones. Since nonnested multigrid methods accept quite arbitrarily related meshes, we may then combine the efficiencies of adaptive refinements and of multigrid algorithms.References
- 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 J. H. Bramble, J. E. Pasciak, and J. Xu, The Analysis of multigrid algorithms with nonnested spaces or non-inherited quadratic forms (preprint).
- Susanne C. Brenner, An optimal-order multigrid method for $\textrm {P}1$ nonconforming finite elements, Math. Comp. 52 (1989), no. 185, 1–15. MR 946598, DOI 10.1090/S0025-5718-1989-0946598-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
- P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR 775683
- W. Hackbusch and U. Trottenberg (eds.), Multigrid methods. II, Lecture Notes in Mathematics, vol. 1228, Springer-Verlag, Berlin, 1986. MR 896053, DOI 10.1007/BFb0072636 —, Multigrid methods, Lecture Notes in Math., vol. 960, Springer-Verlag, Berlin and New York, 1982.
- Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
- Jan Mandel, Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step, Appl. Math. Comput. 19 (1986), no. 1-4, 201–216. Second Copper Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR 849837, DOI 10.1016/0096-3003(86)90104-9
- Stephen F. McCormick (ed.), Multigrid methods, Frontiers in Applied Mathematics, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1987. MR 972752, DOI 10.1137/1.9781611971057
- Petra Peisker, A multilevel algorithm for the biharmonic problem, Numer. Math. 46 (1985), no. 4, 623–634. MR 796649, DOI 10.1007/BF01389663
- P. Peisker and D. Braess, A conjugate gradient method and a multigrid algorithm for Morley’s finite element approximation of the biharmonic equation, Numer. Math. 50 (1987), no. 5, 567–586. MR 880336, DOI 10.1007/BF01408577
- Juhani Pitkäranta and Tuomo Saarinen, A multigrid version of a simple finite element method for the Stokes problem, Math. Comp. 45 (1985), no. 171, 1–14. MR 790640, DOI 10.1090/S0025-5718-1985-0790640-2
- L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483–493. MR 1011446, DOI 10.1090/S0025-5718-1990-1011446-7 —, A nonnested multigrid method for three dimensional boundary value problems: An introduction to NMGTM code, in preparation.
- R. Verfürth, A multilevel algorithm for mixed problems, SIAM J. Numer. Anal. 21 (1984), no. 2, 264–271. MR 736330, DOI 10.1137/0721019
- R. Verfürth, A combined conjugate gradient-multigrid algorithm for the numerical solution of the Stokes problem, IMA J. Numer. Anal. 4 (1984), no. 4, 441–455. MR 768638, DOI 10.1093/imanum/4.4.441
- R. Verfürth, Multilevel algorithms for mixed problems. II. Treatment of the mini-element, SIAM J. Numer. Anal. 25 (1988), no. 2, 285–293. MR 933725, DOI 10.1137/0725020 S. Zhang, Multi-level iterative techniques, Ph. D. thesis, Pennsylvania State University, 1988. —, Successive subdivisions of tetrahedra and multigrid methods on tetrahedral meshes, submitted, also in [19]. —, Multigrid methods for solving biharmonic, ${C^1}$ finite element equations, Numer. Math. 56 (1989), 613-624. —, An optimal order interpolation operator from $H_0^1$ to piecewise linear functions $S_0^1$ on polygons, §6.3 in [19].
- Shangyou Zhang, Optimal-order nonnested multigrid methods for solving finite element equations. I. On quasi-uniform meshes, Math. Comp. 55 (1990), no. 191, 23–36. MR 1023054, DOI 10.1090/S0025-5718-1990-1023054-2
Additional Information
- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp. 55 (1990), 23-36
- MSC: Primary 65N55; Secondary 65F10, 65N30
- DOI: https://doi.org/10.1090/S0025-5718-1990-1023054-2
- MathSciNet review: 1023054