A comparison of adaptive refinement techniques for elliptic problems

ABSTRACT

Adaptive refinement has proved to be a useful tool for reducing the size of the linear system of equations obtained by discretizing partial differential equations. We consider techniques for the adaptive refinement of triangulations used with the finite element method with piecewise linear functions. Several such techniques that differ mainly in the method for dividing triangles and the method for indicating which triangles have the largest error have been developed. We describe four methods for dividing triangles and eight methods for indicating errors. Angle bounds for the triangle division methods are compared. All combinations of triangle divisions and error indicators are compared in a numerical experiment using a population of eight test problems with a variety of difficulties (peaks, boundary layers, singularities, etc.). The comparison is based on the L-infinity norm of the error versus the number of vertices. It is found that all of the methods produce asymptotically optimal grids and that the number of vertices needed for a given error rarely differs by more than a factor of two.

REFERENCES

• 1: BABU~KA, I., AND AZlZ, A.K. On the angle condition in the finite element method. SIAM J. Numer. Anal. 13 (1976), 214-226.
• 2: BABUSKA, I., AND RHEINBOLDT, W. Error estimates for adaptive finite element computations. SIAM J. Numer. Anal. 15 (1978), 736-754.
• 3: BANK, R.E. PLTMG User's Guide, Edition 4.0. Tech. Rep., Dept. of Mathematics, Univ. of California at San Diego, La Jolla, Calif., 1985.
• 4: BANK, R. E., AND SHERMAN, A. H. The use of adaptive grid refinement for badly behaved elliptic partial differential equations. In Advances in Computer Methods for Partial Differential Equations III, R. Vichnevetsky and R. S. Stepleman, Eds. IMACS, New Brunswick, 1979, pp. 33-39.
• 5: BANK, R. E., AND SHERMAN, A.H. An adaptive multilevel method for elliptic boundary value problems. Computing 26 (1981), 91-105.
• 6: BANK, R. E., AND WEISER, A. Some a posteriori error estimators for elliptic partial differential equations. Math. Comput. 44 (1985), 283-301.
• 7: DE, J. P., GAGO, S. R., KELLY, D. W., ZIENKIEWlCZ, O. C., AND BABU~KA, I. A posteriori error analysis and adaptive processes in the finite element method: Part II--Adaptive mesh refinement. Int. J. Numer. Meth. Eng. 19 (1983), 1621-1656.
• 8: FRIED, I. Condition of finite element matrices generated from nonuniform meshes. AIAA J. 10 (1972), 219-221.
• 9: KELLY, D. W., DE, J. P., GAGO, S. R., ZIENKIEWICZ, O. C., AND BABU~KA, I. A posteriori error analysis and adaptive processes in the finite element method: Part I--Error analysis. Int. J. Numer. Meth. Eng. 19 (1983), 1593-1619.
• 10: MITCHELL, W.F. A comparison of adaptive refinement techniques for elliptic problems. Tech. Rep. UIUCDCS-R-87-1375, Dept. of Computer~Science, Univ. of Illinois, Urbana, 1987.
• 11: RICE, J. R., HOUSTIS, E. S., AND DYKSEN, W.R. A population of linear, second order elliptic partial differential equations on rectangular domains. Math. Comput. 36 (1981), 475-484.
• 12: RIVARA, M. C. Mesh refinement processes based on the generalized bisection of simplices. SIAM J. Numer. Anal. 21 (1984), 604-613.
• 13: RIVARA, M. C. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. Int. J. Numer. Meth. Eng. 20 (1984), 745-756.
• 14: Maria-Cecilia Rivara, Design and data structure of fully adaptive, multigrid, finite-element software, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.242-264, Sept. 1984 [doi>10.1145/1271.1274]
• 15: R{VARA, M.C. Adaptive finite element refinement and fully irregular and conforming triangulations. In Accuracy Estimates and Adaptive Refinements in Finite Element Computations, I. Babu~ka, O. C. Zienkiewicz, J. Gago, and E. R. de A. Oliveira, Eds. Wiley, 1986, pp. 359-369.
• 16: ROSENBERG, I. G., AND STENGER, F. A lower bound on the angles of triangles constructed by bisecting the longest side. Math. Comput. 29 (1975), 390-395.
• 17: SEWELL, E.G. Automatic generation of triangulations for piecewise polynomial approximation. Ph.D. dissertation, Purdue Univ., West Lafayette, Ind., 1972.
• 18: SEWELL, E~ G. A finite element program with automatic user-controlled mesh grading. In Advances in Computer Methods for Partial Differential Equations III, R. Vichnevetsky, and R. S. Stepleman, Eds. IMACS, New Brunswick, 1979, pp. 8-10.
• 19: Granville Sewell, Analysis of a Finite Element Method--PDE/PROTRAN, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
• 20: ZIENKIEWICZ, O. C., KELLY, D. W., GAGO, J., AND BABU~KA, I. Hierarchical finite element approaches, error estimates and adaptive refinement. In The Mathematics of Finite Elements and Applications IV, J. R. Whiteman, Ed. Academic Press, Orlando, Fla., 1982, pp. 313-346. {

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods; Elliptic equations

General Terms:
Experimentation