A compiler for variational forms

ABSTRACT

As a key step towards a complete automation of the finite element method, we present a new algorithm for automatic and efficient evaluation of multilinear variational forms. The algorithm has been implemented in the form of a compiler, the FEniCS Form Compiler (FFC). We present benchmark results for a series of standard variational forms, including the incompressible Navier--Stokes equations and linear elasticity. The speedup compared to the standard quadrature-based approach is impressive; in some cases the speedup is as large as a factor of 1000.

REFERENCES

• 1: Arnold, D. N. and Winther, R. 2002. Mixed finite elements for elasticity. Numer. Math. 92, 3, 401--419.
• 2: Bagheri, B. and Scott, R. 2003. Analysa. http://people.cs.uchicago.edu/~ridg/al/aa.html.
• 3: Balay, S., Buschelman, K., Eijkhout, V., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2004. PETSc users manual. Tech. Rep. ANL-95/11 - Revision 2.1.5, Argonne National Laboratory.
• 4: Balay, S., Buschelman, K., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2005a. Anl anl sidl environmentsidl environment. http://www-unix.mcs.anl.gov/ase/.
• 5: Balay, S., Buschelman, K., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2005b. PETSc. http://www.mcs.anl.gov/petsc/.
• 6: Satish Balay , William D. Gropp , Lois Curfman McInnes , Barry F. Smith, Efficient management of parallelism in object-oriented numerical software libraries, Modern software tools for scientific computing, Birkhauser Boston Inc., Cambridge, MA, 1997
• 7: Bangerth, W., Hartmann, R., and Kanschat, G. 2005. deal.II differential equations analysis library. http://www.dealii.org.
• 8: Becker, R. and Rannacher, R. 2001. An optimal control approach to a posteriori error estimation in finite element methods. Acta Numerica 10, 1--102.
• 9: Daniele Boffi, Three-Dimensional Finite Element Methods for the Stokes Problem, SIAM Journal on Numerical Analysis, v.34 n.2, p.664-670, April. 1997 [doi>10.1137/S0036142994270193]
• 10: Brenner, S. C. and Scott, L. R. 1994. The Mathematical Theory of Finite Element Methods. Springer Verlag.
• 11: Brezzi, F., Douglas, Jr., J., and Marini, L. D. 1985. Two families of mixed finite elements for second-order elliptic problems. Numer. Math. 47, 2, 217--235.
• 12: Franco Brezzi , Michel Fortin, Mixed and hybrid finite element methods, Springer-Verlag New York, Inc., New York, NY, 1991
• 13: Castillo, P., Koning, J., Rieben, R., and White, D. 2004. A discrete differential forms framework for computational electromagnetics. Comput. Modeling Eng. Sci. 5, 4, 331--346.
• 14: 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]
• 15: Ciarlet, P. G. 1976. Numerical Analysis of the Finite Element Method. Les Presses de l'Universite de Montreal.
• 16: Crouzeix, M. and Raviart, P. A. 1973. Conforming and nonconforming finite element methods for solving the stationary stokes equations. RAIRO Anal. Numer. 7, 33--76.
• 17: Dular, P. and Geuzaine, C. 2005. GetDP: A general environment for the treatment of discrete problems. http://www.geuz.org/getdp/.
• 18: Dunavant, D. A. 1985. High-Degree efficient symmetrical Gaussian quadrature rules for the triangle. Int. J. Numer. Methods Eng. 21, 6, 1129--1148.
• 19: Eriksson, K., Estep, D., Hansbo, P., and Johnson, C. 1995. Introduction to adaptive methods for differential equations. Acta Numerica 4, 105--158.
• 20: Kenneth Eriksson , D. Estep , P. Hansbo , C. Johnson , K. Eriksson, Computational Differential Equations, Cambridge University Press, New York, NY, 1996
• 21: Eriksson, K., Estep, D., and Johnson, C. 2003. Applied Mathematics: Body and Soul. Vol. III. Springer Verlag.
• 22: Free Software Foundation. 1991. GNU gpl. http://www.gnu.org/copyleft/gpl.html.
• 23: Hoffman, J., Jansson, J., Johnson, C., Knepley, M., Kirby, R. C., Logg, A., and Scott, L. R. 2005. FEniCS. http://www.fenics.org/.
• 24: Hoffman, J., Jansson, J., and Logg, A. 2005. DOLFIN. http://www.fenics.org/dolfin/.
• 25: Hoffman, J. and Logg, A. 2002. DOLFIN: Dynamic object-oriented library for FINite element computation. Tech. Rep. 2002--06, Chalmers Finite Element Center Preprint series.
• 26: Hughes, T. J. R. 1987. The Finite Element Method: Linear Static and Dynamic Finite Element Analysis. Prentice-Hall, Upper Saddle River, NJ.
• 27: Karniadakis, G. E. and Sherwin, S. J. 1999. Spectral/hp element methods for CFD. In Numerical Mathematics and Scientific Computation. Oxford University Press, New York.
• 28: Robert C. Kirby, Algorithm 839: FIAT, a new paradigm for computing finite element basis functions, ACM Transactions on Mathematical Software (TOMS), v.30 n.4, p.502-516, December 2004 [doi>10.1145/1039813.1039820]
• 29: Robert C. Kirby, Optimizing FIAT with level 3 BLAS, ACM Transactions on Mathematical Software (TOMS), v.32 n.2, p.223-235, June 2006 [doi>10.1145/1141885.1141889]
• 30: Robert C. Kirby , Matthew Knepley , Anders Logg , L. Ridgway Scott, Optimizing the Evaluation of Finite Element Matrices, SIAM Journal on Scientific Computing, v.27 n.3, p.741-758, 2005 [doi>10.1137/040607824]
• 31: Kirby, R. C., Knepley, M., and Scott, L. R. 2005b. Evaluation of the action of finite element operators. Submitted to BIT.
• 32: Kirby, R. C., Strout, M. M., Hovland, P., and Scott, L. R. 2005c. Verification of scientific code using rationality analysis. In preparation.
• 33: Hans Petter Langtangen , H. P. Langtangen, Computational Partial Differential Equations: Numerical Methods and Diffpack Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 34: Logg, A. 2004. Automation of computational mathematical modeling. Ph.D. thesis, Chalmers University of Technology, Sweden.
• 35: Long, K. 2003. Sundance, a rapid prototyping tool for parallel PDE-constrained optimization. In Large-Scale PDE-Constrained Optimization. Lecture Notes in Computational Science and Engineering. Springer Verlag.
• 36: Mackie, R. I. 1992. Object-Oriented programming of the finite element method. Int. J. Num. Meth. Eng. 35, 425--436.
• 37: Masters, I., Usmani, A. S., Cross, J. T., and Lewis, R. W. 1997. Finite element analysis of solidification using obect-oriented and parallel techniques. Int. J. Numer. Meth. Eng. 40, 2891--2909.
• 38: Nédélec, J.-C. 1980. Mixed finite elements in R3. Numer. Math. 35, 3, 315--341.
• 39: Pironneau, O., Hecht, F., and Hyaric, A. L. 2005. FreeFEM. http://www.freefem.org/.
• 40: Raviart, P.-A. and Thomas, J. M. 1977. A mixed finite element method for second-order elliptic problems. In Mathematical Aspects of Finite Element Methods; Proceeding of the Conference Consiglio Naz. delle Ricerche (CNR), Rome, held in 1975. Lecture Notes in Mathematics, vol. 606 Springer Verlag, 292--315.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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

General Terms:
Algorithms, Performance

Keywords:
Variational form, automation, compiler, finite element