Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Local and parallel finite element algorithms based on two-grid discretizations

Authors: Jinchao Xu and Aihui Zhou
Journal: Math. Comp. 69 (2000), 881-909
MSC (1991): Primary 65N15, 65N30, 65N55, 65F10
Published electronically: May 19, 1999
MathSciNet review: 1654026
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A number of new local and parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation that, for a solution to some elliptic problems, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. The theoretical tools for analyzing these methods are some local a priori and a posteriori estimates that are also obtained in this paper for finite element solutions on general shape-regular grids. Some numerical experiments are also presented to support the theory.

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

  • 1. Adams R.A.(1975): Sobolev Spaces, Academic Press, New York. MR 56:9247
  • 2. Ainsworth, M. and Oden, J.T.(1993): A unified approach to a posteriori error estimation using element residual methods, Numer. Math., 65, 23-50. MR 95a:65185
  • 3. Axelsson, O. and Layton, W.(1996): A two-level discretization of nonlinear boundary value problems, SIAM J. Numer. Anal., 33, 2359-2374. MR 98c:65181
  • 4. Babuska, I., Duran, R. and Rodriguez, R.(1992): Analysis of the efficiency of an posteriori error estimator for linear triangular finite elements, SIAM J. Numer. Anal., 29, 947-946. MR 93d:65096
  • 5. Babuska, I. and Rheinboldt, C.(1978): Error estimates for adaptive finite element computations, SIAM J. Numer. Anal., 15, 736-754. MR 58:3400
  • 6. Babuska, I., Zienkiewicz, O.C., Gago, J. and Oliveira, E.R. de A. (eds.)(1986): Accuracy Estimates and Adaptive Refinements in Finite Element Computations, Wiley, New York. MR 87j:65004
  • 7. Babuska, I., Strouboulis, T. and Gangaraj, S.K.(1997): A posteriori estimation of the error in the recovered derivatives of the finite element solution, Comput. Methods Appl. Mech. Engrg., 150, 369-396. CMP 98:06
  • 8. Babuska, I., Strouboulis, T., Gangaraj, S.K. and Upadhyay, C.S.(1997): Pollution error in the $h-$version of the finite element method and the local quality of the recovered derivatives, Comput. Methods Appl. Mech. Engrg., 140, 1-37. MR 97i:73092
  • 9. Babuska, I., Strouboulis, T. and Upadhyay, C.S.(1994): A model study of the quality of a posteriori error estimators for linear elliptic problems. Error estimation in the interior of patchwise uniform grids of triangles, Comput. Methods Appl.Mech. Engrg., 114, 307-378. MR 95d:65093
  • 10. Bank, R.E.(1996): Hierarchical bases and the finite element method, Acta Numerica, 5, 1-43. CMP 98:14
  • 11. Bank, R.E.(1998): A simple analysis of some a posteriori error estimates, Appl. Numer. Math., 26, 153-164. CMP 98:08
  • 12. Bank, R.E. and Holst, M.(1998): A new paradigm for parallel adaptive meshing algorithms (manuscript).
  • 13. Bank, R.E. and Smith, R.K.(1993): A posteriori error estimates based on hierarchical bases, SIAM J. Numer. Anal., 30, 921-935. MR 95f:65212
  • 14. Bank, R.E. and Smith, R.K.(1997): Mesh smoothing using a posteriori error estimates, SIAM J. Numer. Anal., 34, 979-997. MR 98M:65162
  • 15. Bank, R.E. and Weiser, A.(1985): Some a posteriori error estimates for elliptic partial differential equations, Math. Comp., 44, 283-301. MR 86g:65207
  • 16. Bedivan, D.M.(1995): A two-grid method for solving elliptic problems with inhomogeneous boundary conditions, Comput. Math. Appl., 29, 59-66. MR 95k:65103
  • 17. Blum, H., Lin, Q. and Rannacher, R.(1986): Asymptotic error expansion and Richardson extrapolation for linear finite elements, Numer. Math., 49, 11-38. MR 87m:65172
  • 18. Bornemann, F.A., Erdmann, B. and Kornhuber, R.(1996): A posteriori error estimates for elliptic problems in two and three space dimensions, SIAM J. Numer. Anal., 33, 1188-1204. MR 98a:65161
  • 19. Bramble, J.H.(1993): Multigrid Methods, Pitman Research Notes in Mathematics, 294, London Co-published in the USA with Wiley, New York. MR 95b:65002
  • 20. Bramble, J.H., Ewing, R.E., Parashkevov, R.R. and Pasciak, J.E.(1992): Domain decomposition methods for problems with partial refinement, SIAM J. Sci. Stat. Comp., 13, 397-410. MR 92i:65179
  • 21. Bramble, J.H., Ewing, R.E., Pasciak, J.E. and Schatz, A.H.(1988): A preconditioning technique for the efficient solution of problems with local grid refinement, Comp. Meth. Appl. Mech. Eng., 67, 149-159.
  • 22. Chan, T. and Mathew, T.(1994): Domain decomposition algorithms, Acta Numerica, 3, 61-143. MR 95f:65214
  • 23. Ciarlet, P.G. and Lions J.L.(1991): Handbook of Numerical Analysis, Vol.II, Finite Element Methods (Part I), North-Holland. MR 92f:65001
  • 24. Dawson, C.N. and Wheeler, M.F.(1994): Two-grid methods for mixed finite element approximations of nonlinear parabolic equations, Contemp. Math., 180, 191-203. MR 95j:65117
  • 25. Dawson, C.N., Wheeler, M.F. and Woodward, C.S.(1998): A two-grid finite difference scheme for nonlinear parabolic equations, SIAM J. Numer. Anal., 35, 435-452. MR 99b:65097
  • 26. Eriksson, K., Estep, D., Hansbo, P. and Johnson, C.(1995): Introduction to adaptive methods for differential equations, Acta Numerica, 105-158. MR 96k:65057
  • 27. Eriksson, K., Estep, D., Hansbo, P. and Johnson, C.(1996): Computational Differential Equations, Cambridge University Press. MR 97m:65006
  • 28. Eriksson, K. and Johnson, C.(1991): Adaptive finite element methods for parabolic problems I: a linear model problem, SIAM J. Numer. Anal., 28, 43-77. MR 91m:65274
  • 29. Eriksson, K. and Johnson, C.(1995): Adaptive finite element methods for parabolic problems IV: Nonlinear problems, SIAM J. Numer. Anal., 32, 1729-1749. MR 96i:65081
  • 30. Grisvard, P.(1985): Elliptic Problems in Nonsmooth Domains, Pitman, Boston, MA. MR 86m:35044
  • 31. Hackbusch, W.(1985): Multigrid Methods and Applications, Springer, New York. MR 87e:65082
  • 32. Johnson, C.(1990): Adaptive finite element methods for diffusion and convection problems, Comp. Methods Appl. Mech. Engrg., 82, 301-322. MR 91k:65134
  • 33. Layton, W. and Lenferink, W.(1995): Two-level Picard and modified Picard methods for the Navier-Stokes equations, Appl. Math. Comp., 69, 263-274. MR 95m:65191
  • 34. Marion, M. and Xu, J.(1995): Error estimates on a new nonlinear Galerkin method based on two-grid finite elements, SIAM J. Numer. Anal., 32, 1170-1184. MR 96f:65136
  • 35. Nitsche, J. and Schatz, A.H.(1974): Interior estimates for Ritz-Galerkin methods, Math. Comp., 28, 937-955. MR 51:9525
  • 36. Nochetto, R. H.(1995): Pointwise a posteriori error estimates for elliptic problems on highly graded meshes, Math. Comp., 64, 1-22. MR 95c:65172
  • 37. Rannacher, R. and Scott, R.(1982): Some optimal error estimates for piecewise linear finite element approximations, Math. Comp., 38, 437-445. MR 83e:65180
  • 38. Schatz, A.H.(1998): Pointwise error estimates and asymptotic error expansion inequalities for the finite element method on irregular grids: Part I. Global estimates, Math. Comp., 67, 877-899. MR 98j:65082
  • 39. Schatz, A.H. and Wahlbin, L.B.(1977): Interior maximum-norm estimates for finite element methods, Math. Comp., 31, 414-442. MR 55:4748
  • 40. Schatz, A.H. and Wahlbin, L.B.(1995): Interior maximum-norm estimates for finite element methods, Part II, Math. Comp., 64, 907-928. MR 95j:65143
  • 41. Schatz, A.H. and Wang, J.(1996): Some new error estimates for Ritz-Galerkin methods with minimal regularity assumptions, Math. Comp., 65, 19-27. MR 96d:65190
  • 42. Utnes, T.(1997): Two-grid finite element formulations of the incompressible Navier-Stokes equations, Comm. Numer. Methods Engrg., 34, 675-684. MR 98d:76110
  • 43. Verfürth, R.(1994): A posteriori error estimates for nonlinear problems. Finite element discretizations of elliptic equations, Math. Comp., 62, 445-475. MR 94j:65136
  • 44. Verfürth, R.(1995): A posteriori error estimates for nonlinear problems. Finite element discretizations of parabolic equations, Bericht Nr. 180, Fakultät für Mathematik, Ruhr-Universität Bochum.
  • 45. Verfürth, R.(1996): A Review of A-Posteriori Error Estimation and Adaptive Mesh Refinement, Wiley-Teubner.
  • 46. Wahlbin, L.B.(1991): Local behavior in finite element methods, in [23], pp. 355-522. MR 92f:65001
  • 47. Wahlbin, L.B.(1995): Superconvergence in Galerkin Finite Element Methods, Vol. 1605, Lecture Notes in Math., Springer. MR 98j:65083
  • 48. Xu, J.(1992): A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal., 29, 303-319. MR 92k:65063
  • 49. Xu, J.(1992): Iterative methods by space decomposition and subspace correction, SIAM Review, 34, 4, 581-613. MR 93k:65029
  • 50. Xu, J.(1994): A novel two-grid method for semilinear equations, SIAM J. Sci. Comput., 15, 231-237. MR 94m:65178
  • 51. Xu, J.(1996): Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal., 33, 1759-1777. MR 97i:65169
  • 52. Xu, J. and Zou, J.(1998): Some non-overlapping domain decomposition methods, SIAM Review 40, 4, 857-914.
  • 53. Yserentant, H.(1993): Old and new proofs for multigrid algorithms, Acta Numerica, 2, 285-326. MR 94i:65128
  • 54. Zhou, A., Liem, C.L., Shih, T.M. and Lü, T.(1998): Error analysis on bi-parameter finite elements, Comput. Methods Appl. Mech. Engrg., 158, 329-339. CMP 98:14

Similar Articles

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

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

Additional Information

Jinchao Xu
Affiliation: Center for Computational Mathematics and Applications, Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802

Aihui Zhou
Affiliation: Institute of Systems Science, Academia Sinica, Beijing 100080, China

Keywords: Adaptive, finite elements, local a priori and a posteriori error estimates, nonsymmetric, parallel algorithm, two-grid method
Received by editor(s): July 21, 1998
Published electronically: May 19, 1999
Additional Notes: This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 through Penn State and Center for Computational Mathematics and Applications, The Pennsylvania State University.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society