Mathematics of Computation

Author(s): Jinchao Xu; Aihui Zhou.
Journal: Math. Comp. 69 (2000), 881-909.
MSC (1991): Primary 65N15, 65N30, 65N55, 65F10
Posted: May 19, 1999
Retrieve article in: PDF
This article is available free of charge

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.

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 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

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

Jinchao Xu
Affiliation: Center for Computational Mathematics and Applications, Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
Email: xu@math.psu.edu

Aihui Zhou
Affiliation: Institute of Systems Science, Academia Sinica, Beijing 100080, China
Email: azhou@bamboo.iss.ac.cn

DOI: 10.1090/S0025-5718-99-01149-7
PII: S 0025-5718(99)01149-7
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
Posted: 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.
Copyright of article: Copyright 2000, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS