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

Xu, Jinchao; Zhou, Aihui

doi:10.1090/S0025-5718-99-01149-7

Local and parallel finite element algorithms based on two-grid discretizations
HTML articles powered by AMS MathViewer

by Jinchao Xu and Aihui Zhou HTML | PDF

Math. Comp. 69 (2000), 881-909 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 0450957
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.