Data structures and requirements for hp finite element software

ABSTRACT

Finite element methods approximate solutions of partial differential equations by restricting the problem to a finite dimensional function space. In hp adaptive finite element methods, one defines these discrete spaces by choosing different polynomial degrees for the shape functions defined on a locally refined mesh.

Although this basic idea is quite simple, its implementation in algorithms and data structures is challenging. It has apparently not been documented in the literature in its most general form. Rather, most existing implementations appear to be for special combinations of finite elements, or for discontinuous Galerkin methods.

In this article, we discuss generic data structures and algorithms used in the implementation of hp methods for arbitrary elements, and the complications and pitfalls one encounters. As a consequence, we list the information a description of a finite element has to provide to the generic algorithms for it to be used in an hp context. We support our claim that our reference implementation is efficient using numerical examples in two dimensions and three dimensions, and demonstrate that the hp-specific parts of the program do not dominate the total computing time. This reference implementation is also made available as part of the Open Source deal.II finite element library.

REFERENCES

• 1: Ainsworth, M. and Senior, B. 1997. Aspects of an adaptive hp-finite element method: Adaptive strategy, conforming approximation and efficient solvers. Comput. Methods Appl. Mech. Engrg. 150, 65--87.
• 2: Ainsworth, M. and Senior, B. 1999. hp-Finite element procedures on non-uniform geometric meshes: Adaptivity and constrained approximation. In Grid Generation and Adaptive Algorithms, M. Bern, J. Flaherty, and M. Luskin, Eds. IMA Vol. Math. Appl., vol. 113. Springer, Berlin, Germany, 1--27.
• 3: Babuška, I. 1981. Error estimates for the combined h and p version of finite element method. Numer. Math. 37, 252--277.
• 4: W. Bangerth , R. Hartmann , G. Kanschat, deal.II—A general-purpose object-oriented finite element library, ACM Transactions on Mathematical Software (TOMS), v.33 n.4, p.24-es, August 2007 [doi>10.1145/1268776.1268779]
• 5: Bangerth, W., Hartmann, R., and Kanschat, G. 2008. deal.II Differential Equations Analysis Library, Technical Reference. http://www.dealii.org/.
• 6: Franco Brezzi , Michel Fortin, Mixed and hybrid finite element methods, Springer-Verlag New York, Inc., New York, NY, 1991
• 7: Carey, G. F. 1997. Computational Grids: Generation, Adaptation and Solution Strategies. Taylor & Francis, London, U.K.
• 8: Paul Castillo , Robert Rieben , Daniel White, FEMSTER: An object-oriented class library of high-order discrete differential forms, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.425-457, December 2005 [doi>10.1145/1114268.1114269]
• 9: Ciarlet, P. G. 1978. The Finite Element Method for Elliptic Problems, 1st ed. Studies in Mathematics and its Applications, vol. 4. North-Holland, Amsterdam, The Netherlands, New York, NY, Oxford, U.K.
• 10: Demkowicz, L. 2006. Computing with hp-Adaptive Finite Elements. Volume 1: One and Two Dimensional Elliptic and Maxwell Problems. Chapman & Hall, London, U.K.
• 11: Frauenfelder, P. and Lage, C. 2002. Concepts—An object-oriented software package for partial differential equations. Math. Model. Numer. Anal. 36, 937--951.
• 12: Gilbarg, D. and Trudinger, N. S. 1983. Elliptic Partial Differential Equations of Second Order, Second ed. Springer, Heidelberg, Germany.
• 13: Guo, B. and Babuška, I. 1986a. The h-p version of the finite element method. Part I: The basic approximation results. Comp. Mech. 1, 21--41.
• 14: Guo, B. and Babuška, I. 1986b. The h-p version of the finite element method. Part II: The general results and application. Comp. Mech. 1, 203--220.
• 15: Houston, P., Schötzau, D., and Wihler, T. P. 2007. Energy norm a posteriori error estimation of hp-adaptive discontinuous Galerkin methods for elliptic problems. Math. Models Meth. Appl. Sci. 17, 33--62.
• 16: Houston, P. and Süli, E. 2005. A note on the design of hp-adaptive finite element methods for elliptic partial differential equations. Comp. Meth. Appl. Mech. Engrg. 194, 229--243.
• 17: Houston, P., Süli, E., and Wihler, T. P. 2008. A posteriori error analysis of hp-version discontinuous Galerkin finite element methods for second-order quasilinear elliptic problems. IMA J. Numer. Anal., In press.
• 18: Hwang, K., Pan, T., Joshi, A., Rasmussen, J. C., Bangerth, W., and Sevick-Muraca, E. M. 2006. Influence of excitation light rejection on forward model mismatch in optical tomography. Phys. Med. Biol. 51, 5889--5902.
• 19: Robert C. Kirby , Anders Logg, A compiler for variational forms, ACM Transactions on Mathematical Software (TOMS), v.32 n.3, p.417-444, September 2006 [doi>10.1145/1163641.1163644]
• 20: Kirby, R. and Logg, A. 2006b. Optimizing the FEniCS form compiler FFC: Efficient pretabulation of integrals. ACM Trans. Math. Softw.. Submitted.
• 21: Benjamin S. Kirk , John W. Peterson , Roy H. Stogner , Graham F. Carey, libMesh: a C++ library for parallel adaptive mesh refinement/coarsening simulations, Engineering with Computers, v.22 n.3, p.237-254, December 2006 [doi>10.1007/s00366-006-0049-3]
• 22: Nedelec, J.-C. 1980. Mixed finite elements in R³. Numer. Math. 35, 315--341.
• 23: Lars Pesch , Alexander Bell , Henk Sollie , Vijaya R. Ambati , Onno Bokhove , Jaap J. W. Van Der Vegt, hpGEM---A software framework for discontinuous Galerkin finite element methods, ACM Transactions on Mathematical Software (TOMS), v.33 n.4, p.23-es, August 2007 [doi>10.1145/1268776.1268778]
• 24: Werner C. Rheinboldt , Charles K. Mesztenyi, On a Data Structure for Adaptive Finite Element Mesh Refinements, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.166-187, June 1980 [doi>10.1145/355887.355891]
• 25: Rivara, M. C. 1984. Mesh refinement processes based on the generalized bisection of simplices. SIAM J. Numer. Anal. 21, 604--613.
• 26: Pavel Šolín , Jakub ervený , Ivo Doleel, Arbitrary-level hanging nodes and automatic adaptivity in the hp-FEM, Mathematics and Computers in Simulation, v.77 n.1, p.117-132, February, 2008 [doi>10.1016/j.matcom.2007.02.011]
• 27: Šolín, P., Segeth, K., and Doležel, I. 2003. Higher-Order Finite Element Methods. Chapman & Hall, London, U.K./CRC Press, Orlando, FL.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Design

Keywords:
hp finite element methods, Object orientation, data structures, finite element software, software design