×

Local and parallel finite element algorithms based on two-grid discretizations. (English) Zbl 0948.65122

The authors consider a convex polygonal domain \(\Omega\subset \mathbb{R}^2\) and the elliptic model equation \(-\Delta u+ b\cdot \nabla u= f\) in \(\Omega\) under the boundary condition \(u= 0\) on \(\partial\Omega\). It is supposed that a coarse grid approximation is good enough to capture the global component of the solution. Then the authors suggest to improve it on much finer grids in subdomains by some local and parallel procedure. The mathematical justification of such methods is connected with the interesting a priori inequality \[ \|u- P_h u\|_{1,D}\leq K\{h^s_{\Omega_0}\|u\|_{s+1,\Omega_0}+ h^{s+ \alpha}_\Omega\|u\|_{s+1,\Omega}\}, \] where \(D\subset\subset \Omega_0\subset\subset \Omega\), \(h_{\Omega_0}\) corresponds to the fine grid on \(\overline\Omega_0\), and \(h_\Omega\) to the original coarse grid on \(\overline\Omega\). Numerical experiments with \(h\asymp 10^{-3}\) in the unit square confirm good perspectives of such methods. Adaptation of grids is discussed as well.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
65N15 Error bounds for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Robert A. Adams, Sobolev spaces, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1975. Pure and Applied Mathematics, Vol. 65. · Zbl 0314.46030
[2] 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. · Zbl 0797.65080 · doi:10.1007/BF01385738
[3] O. Axelsson and W. Layton, A two-level discretization of nonlinear boundary value problems, SIAM J. Numer. Anal. 33 (1996), no. 6, 2359 – 2374. · Zbl 0866.65077 · doi:10.1137/S0036142993247104
[4] 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. · Zbl 0759.65069 · doi:10.1137/0729058
[5] I. Babuška and W. C. Rheinboldt, Error estimates for adaptive finite element computations, SIAM J. Numer. Anal. 15 (1978), no. 4, 736 – 754. · Zbl 0398.65069 · doi:10.1137/0715049
[6] I. Babuška, O. C. Zienkiewicz, J. Gago, and E. R. de A. Oliveira , 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. · Zbl 0663.65001
[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] I. Babuška, T. Strouboulis, S. K. Gangaraj, and C. S. Upadhyay, Pollution error in the \?-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. · Zbl 0896.73055 · doi:10.1016/S0045-7825(96)01013-4
[9] 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. · doi:10.1016/0045-7825(94)90177-5
[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). · Zbl 1028.65104
[13] 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. · Zbl 0787.65078 · doi:10.1137/0730048
[14] Randolph E. Bank and R. Kent Smith, Mesh smoothing using a posteriori error estimates, SIAM J. Numer. Anal. 34 (1997), no. 3, 979 – 997. · Zbl 0873.65092 · doi:10.1137/S0036142994265292
[15] R. E. Bank and A. Weiser, Some a posteriori error estimators for elliptic partial differential equations, Math. Comp. 44 (1985), no. 170, 283 – 301. · Zbl 0569.65079
[16] D. M. Bedivan, A two-grid method for solving elliptic problems with inhomogeneous boundary conditions, Comput. Math. Appl. 29 (1995), no. 6, 59 – 66. · Zbl 0824.65107 · doi:10.1016/0898-1221(95)00007-L
[17] 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. · Zbl 0594.65082 · doi:10.1007/BF01389427
[18] 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. · Zbl 0863.65069 · doi:10.1137/0733059
[19] 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. · Zbl 0786.65094
[20] 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. · Zbl 0746.65084 · doi:10.1137/0913021
[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. · Zbl 0619.76113
[22] Tony F. Chan and Tarek P. Mathew, Domain decomposition algorithms, Acta numerica, 1994, Acta Numer., Cambridge Univ. Press, Cambridge, 1994, pp. 61 – 143. · Zbl 0809.65112 · doi:10.1017/S0962492900002427
[23] P. G. Ciarlet and J.-L. Lions , Handbook of numerical analysis. Vol. II, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. · Zbl 0712.65091
[24] 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. · Zbl 0817.65080 · doi:10.1090/conm/180/01971
[25] 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. · Zbl 0927.65107 · doi:10.1137/S0036142995293493
[26] 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. · Zbl 0829.65122 · doi:10.1017/S0962492900002531
[27] K. Eriksson, D. Estep, P. Hansbo, and C. Johnson, Computational differential equations, Cambridge University Press, Cambridge, 1996. · Zbl 0946.65049
[28] 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. · Zbl 0732.65093 · doi:10.1137/0728003
[29] 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. · Zbl 0835.65116 · doi:10.1137/0732078
[30] P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. · Zbl 0695.35060
[31] Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. · Zbl 0595.65106
[32] 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). · Zbl 0717.76078 · doi:10.1016/0045-7825(90)90169-M
[33] 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. · Zbl 0828.76017 · doi:10.1016/0096-3003(94)00134-P
[34] 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. · Zbl 0853.65092 · doi:10.1137/0732054
[35] Joachim A. Nitsche and Alfred H. Schatz, Interior estimates for Ritz-Galerkin methods, Math. Comp. 28 (1974), 937 – 958. · Zbl 0298.65071
[36] Ricardo H. Nochetto, Pointwise a posteriori error estimates for elliptic problems on highly graded meshes, Math. Comp. 64 (1995), no. 209, 1 – 22. · Zbl 0920.65063
[37] Rolf Rannacher and Ridgway Scott, Some optimal error estimates for piecewise linear finite element approximations, Math. Comp. 38 (1982), no. 158, 437 – 445. · Zbl 0483.65007
[38] 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. · Zbl 0905.65105
[39] A. H. Schatz and L. B. Wahlbin, Interior maximum norm estimates for finite element methods, Math. Comp. 31 (1977), no. 138, 414 – 442. · Zbl 0364.65083
[40] A. H. Schatz and L. B. Wahlbin, Interior maximum-norm estimates for finite element methods. II, Math. Comp. 64 (1995), no. 211, 907 – 928. · Zbl 0826.65091
[41] 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. · Zbl 0856.65129
[42] T. Utnes, Two-grid finite element formulations of the incompressible Navier-Stokes equations, Comm. Numer. Methods Engrg. 13 (1997), no. 8, 675 – 684. , https://doi.org/10.1002/(SICI)1099-0887(199708)13:83.0.CO;2-N · Zbl 0883.76052
[43] R. Verfürth, A posteriori error estimates for nonlinear problems. Finite element discretizations of elliptic equations, Math. Comp. 62 (1994), no. 206, 445 – 475. · Zbl 0799.65112
[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. · Zbl 0874.65082
[45] Verfürth, R.(1996): A Review of A-Posteriori Error Estimation and Adaptive Mesh Refinement, Wiley-Teubner. · Zbl 0853.65108
[46] P. G. Ciarlet and J.-L. Lions , Handbook of numerical analysis. Vol. II, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. · Zbl 0712.65091
[47] Lars B. Wahlbin, Superconvergence in Galerkin finite element methods, Lecture Notes in Mathematics, vol. 1605, Springer-Verlag, Berlin, 1995. · Zbl 0826.65092
[48] Jinchao Xu, A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal. 29 (1992), no. 2, 303 – 319. · Zbl 0756.65050 · doi:10.1137/0729020
[49] Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581 – 613. · Zbl 0788.65037 · doi:10.1137/1034116
[50] Jinchao Xu, A novel two-grid method for semilinear elliptic equations, SIAM J. Sci. Comput. 15 (1994), no. 1, 231 – 237. · Zbl 0795.65077 · doi:10.1137/0915016
[51] Jinchao Xu, Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal. 33 (1996), no. 5, 1759 – 1777. · Zbl 0860.65119 · doi:10.1137/S0036142992232949
[52] Xu, J. and Zou, J.(1998): Some non-overlapping domain decomposition methods, SIAM Review 40, 4, 857-914. · Zbl 0913.65115
[53] Harry Yserentant, Old and new convergence proofs for multigrid methods, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 285 – 326. · Zbl 0788.65108 · doi:10.1017/S0962492900002385
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.