Local and parallel finite element algorithms based on two-grid discretizations
HTML articles powered by AMS MathViewer
- by Jinchao Xu and Aihui Zhou;
- Math. Comp. 69 (2000), 881-909
- DOI: https://doi.org/10.1090/S0025-5718-99-01149-7
- Published electronically: May 19, 1999
- HTML | PDF | Request permission
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
- Robert A. Adams, Sobolev spaces, Pure and Applied Mathematics, Vol. 65, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 450957
- Mark Ainsworth and J. Tinsley Oden, A unified approach to a posteriori error estimation using element residual methods, Numer. Math. 65 (1993), no. 1, 23–50. MR 1217437, DOI 10.1007/BF01385738
- O. Axelsson and W. Layton, A two-level discretization of nonlinear boundary value problems, SIAM J. Numer. Anal. 33 (1996), no. 6, 2359–2374. MR 1427468, DOI 10.1137/S0036142993247104
- Ivo Babuška, Ricardo Durán, and Rodolfo Rodríguez, Analysis of the efficiency of an a posteriori error estimator for linear triangular finite elements, SIAM J. Numer. Anal. 29 (1992), no. 4, 947–964. MR 1173179, DOI 10.1137/0729058
- I. Babuška and W. C. Rheinboldt, Error estimates for adaptive finite element computations, SIAM J. Numer. Anal. 15 (1978), no. 4, 736–754. MR 483395, DOI 10.1137/0715049
- I. Babuška, O. C. Zienkiewicz, J. Gago, and E. R. de A. Oliveira (eds.), Accuracy estimates and adaptive refinements in finite element computations, Wiley Series in Numerical Methods in Engineering, John Wiley & Sons, Ltd., Chichester, 1986. Lectures presented at the international conference held in Lisbon, June 1984; A Wiley-Interscience Publication. MR 879442
- 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.
- I. Babuška, T. Strouboulis, S. K. Gangaraj, and C. S. Upadhyay, 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 (1997), no. 1-2, 1–37. MR 1423455, DOI 10.1016/S0045-7825(96)01013-4
- I. Babuška, T. Strouboulis, and C. S. Upadhyay, 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 (1994), no. 3-4, 307–378. MR 1277482, DOI 10.1016/0045-7825(94)90177-5
- Bank, R.E.(1996): Hierarchical bases and the finite element method, Acta Numerica, 5, 1-43.
- Bank, R.E.(1998): A simple analysis of some a posteriori error estimates, Appl. Numer. Math., 26, 153-164.
- Bank, R.E. and Holst, M.(1998): A new paradigm for parallel adaptive meshing algorithms (manuscript).
- Randolph E. Bank and R. Kent Smith, A posteriori error estimates based on hierarchical bases, SIAM J. Numer. Anal. 30 (1993), no. 4, 921–935. MR 1231320, DOI 10.1137/0730048
- Randolph E. Bank and R. Kent Smith, Mesh smoothing using a posteriori error estimates, SIAM J. Numer. Anal. 34 (1997), no. 3, 979–997. MR 1451110, DOI 10.1137/S0036142994265292
- R. E. Bank and A. Weiser, Some a posteriori error estimators for elliptic partial differential equations, Math. Comp. 44 (1985), no. 170, 283–301. MR 777265, DOI 10.1090/S0025-5718-1985-0777265-X
- D. M. Bedivan, A two-grid method for solving elliptic problems with inhomogeneous boundary conditions, Comput. Math. Appl. 29 (1995), no. 6, 59–66. MR 1317859, DOI 10.1016/0898-1221(95)00007-L
- H. Blum, Q. Lin, and R. Rannacher, Asymptotic error expansion and Richardson extrapolation for linear finite elements, Numer. Math. 49 (1986), no. 1, 11–37. MR 847015, DOI 10.1007/BF01389427
- Folkmar A. Bornemann, Bodo Erdmann, and Ralf Kornhuber, A posteriori error estimates for elliptic problems in two and three space dimensions, SIAM J. Numer. Anal. 33 (1996), no. 3, 1188–1204. MR 1393909, DOI 10.1137/0733059
- James H. Bramble, Multigrid methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. MR 1247694
- James H. Bramble, Richard E. Ewing, Rossen R. Parashkevov, and Joseph E. Pasciak, Domain decomposition methods for problems with partial refinement, SIAM J. Sci. Statist. Comput. 13 (1992), no. 1, 397–410. MR 1145193, DOI 10.1137/0913021
- 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.
- Tony F. Chan and Tarek P. Mathew, Domain decomposition algorithms, Acta numerica, 1994, Acta Numer., Cambridge Univ. Press, Cambridge, 1994, pp. 61–143. MR 1288096, DOI 10.1017/S0962492900002427
- P. G. Ciarlet and J.-L. Lions (eds.), Handbook of numerical analysis. Vol. II, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. MR 1115235
- Clint N. Dawson and Mary F. Wheeler, Two-grid methods for mixed finite element approximations of nonlinear parabolic equations, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 191–203. MR 1312392, DOI 10.1090/conm/180/01971
- Clint N. Dawson, Mary F. Wheeler, and Carol S. Woodward, A two-grid finite difference scheme for nonlinear parabolic equations, SIAM J. Numer. Anal. 35 (1998), no. 2, 435–452. MR 1618822, DOI 10.1137/S0036142995293493
- Kenneth Eriksson, Don Estep, Peter Hansbo, and Claes Johnson, Introduction to adaptive methods for differential equations, Acta numerica, 1995, Acta Numer., Cambridge Univ. Press, Cambridge, 1995, pp. 105–158. MR 1352472, DOI 10.1017/S0962492900002531
- K. Eriksson, D. Estep, P. Hansbo, and C. Johnson, Computational differential equations, Cambridge University Press, Cambridge, 1996. MR 1414897
- Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. I. A linear model problem, SIAM J. Numer. Anal. 28 (1991), no. 1, 43–77. MR 1083324, DOI 10.1137/0728003
- Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. IV. Nonlinear problems, SIAM J. Numer. Anal. 32 (1995), no. 6, 1729–1749. MR 1360457, DOI 10.1137/0732078
- P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR 775683
- 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
- Claes Johnson, Adaptive finite element methods for diffusion and convection problems, Comput. Methods Appl. Mech. Engrg. 82 (1990), no. 1-3, 301–322. Reliability in computational mechanics (Austin, TX, 1989). MR 1077659, DOI 10.1016/0045-7825(90)90169-M
- W. Layton and W. Lenferink, Two-level Picard and modified Picard methods for the Navier-Stokes equations, Appl. Math. Comput. 69 (1995), no. 2-3, 263–274. MR 1326676, DOI 10.1016/0096-3003(94)00134-P
- Martine Marion and Jinchao Xu, Error estimates on a new nonlinear Galerkin method based on two-grid finite elements, SIAM J. Numer. Anal. 32 (1995), no. 4, 1170–1184. MR 1342288, DOI 10.1137/0732054
- Joachim A. Nitsche and Alfred H. Schatz, Interior estimates for Ritz-Galerkin methods, Math. Comp. 28 (1974), 937–958. MR 373325, DOI 10.1090/S0025-5718-1974-0373325-9
- Ricardo H. Nochetto, Pointwise a posteriori error estimates for elliptic problems on highly graded meshes, Math. Comp. 64 (1995), no. 209, 1–22. MR 1270622, DOI 10.1090/S0025-5718-1995-1270622-3
- Rolf Rannacher and Ridgway Scott, Some optimal error estimates for piecewise linear finite element approximations, Math. Comp. 38 (1982), no. 158, 437–445. MR 645661, DOI 10.1090/S0025-5718-1982-0645661-4
- Alfred H. Schatz, Pointwise error estimates and asymptotic error expansion inequalities for the finite element method on irregular grids. I. Global estimates, Math. Comp. 67 (1998), no. 223, 877–899. MR 1464148, DOI 10.1090/S0025-5718-98-00959-4
- A. H. Schatz and L. B. Wahlbin, Interior maximum norm estimates for finite element methods, Math. Comp. 31 (1977), no. 138, 414–442. MR 431753, DOI 10.1090/S0025-5718-1977-0431753-X
- A. H. Schatz and L. B. Wahlbin, Interior maximum-norm estimates for finite element methods. II, Math. Comp. 64 (1995), no. 211, 907–928. MR 1297478, DOI 10.1090/S0025-5718-1995-1297478-7
- Alfred H. Schatz and Jun Ping Wang, Some new error estimates for Ritz-Galerkin methods with minimal regularity assumptions, Math. Comp. 65 (1996), no. 213, 19–27. MR 1308460, DOI 10.1090/S0025-5718-96-00649-7
- T. Utnes, Two-grid finite element formulations of the incompressible Navier-Stokes equations, Comm. Numer. Methods Engrg. 13 (1997), no. 8, 675–684. MR 1466044, DOI 10.1002/(SICI)1099-0887(199708)13:8<675::AID-CNM98>3.0.CO;2-N
- R. Verfürth, A posteriori error estimates for nonlinear problems. Finite element discretizations of elliptic equations, Math. Comp. 62 (1994), no. 206, 445–475. MR 1213837, DOI 10.1090/S0025-5718-1994-1213837-1
- 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.
- Verfürth, R.(1996): A Review of A-Posteriori Error Estimation and Adaptive Mesh Refinement, Wiley-Teubner.
- P. G. Ciarlet and J.-L. Lions (eds.), Handbook of numerical analysis. Vol. II, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. MR 1115235
- Lars B. Wahlbin, Superconvergence in Galerkin finite element methods, Lecture Notes in Mathematics, vol. 1605, Springer-Verlag, Berlin, 1995. MR 1439050, DOI 10.1007/BFb0096835
- Jinchao Xu, A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal. 29 (1992), no. 2, 303–319. MR 1154268, DOI 10.1137/0729020
- Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
- Jinchao Xu, A novel two-grid method for semilinear elliptic equations, SIAM J. Sci. Comput. 15 (1994), no. 1, 231–237. MR 1257166, DOI 10.1137/0915016
- Jinchao Xu, Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal. 33 (1996), no. 5, 1759–1777. MR 1411848, DOI 10.1137/S0036142992232949
- Xu, J. and Zou, J.(1998): Some non-overlapping domain decomposition methods, SIAM Review 40, 4, 857-914.
- Harry Yserentant, Old and new convergence proofs for multigrid methods, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 285–326. MR 1224685, DOI 10.1017/S0962492900002385
- 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.
Bibliographic Information
- Jinchao Xu
- Affiliation: Center for Computational Mathematics and Applications, Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
- MR Author ID: 228866
- Email: xu@math.psu.edu
- Aihui Zhou
- Affiliation: Institute of Systems Science, Academia Sinica, Beijing 100080, China
- Email: azhou@bamboo.iss.ac.cn
- 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.
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 69 (2000), 881-909
- MSC (1991): Primary 65N15, 65N30, 65N55, 65F10
- DOI: https://doi.org/10.1090/S0025-5718-99-01149-7
- MathSciNet review: 1654026