Efficient compilation of a class of variational forms

ABSTRACT

We investigate the compilation of general multilinear variational forms over affines simplices and prove a representation theorem for the representation of the element tensor (element stiffness matrix) as the contraction of a constant reference tensor and a geometry tensor that accounts for geometry and variable coefficients. Based on this representation theorem, we design an algorithm for efficient pretabulation of the reference tensor. The new algorithm has been implemented in the FEniCS Form Compiler (FFC) and improves on a previous loop-based implementation by several orders of magnitude, thus shortening compile-times and development cycles for users of FFC.

REFERENCES

• 1: Bagheri, B. and Scott, L. R. 2003. Analysa. http://people.cs.uchicago.edu/~ridg/al/aa.html.
• 2: 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.
• 3: Balay, S., Buschelman, K., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2006. PETSc. http://www.mcs.anl.gov/petsc/.
• 4: 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
• 5: Bangerth, W., Hartmann, R., and Kanschat, G. 2006. deal.II Differential Equations Analysis Library. http://www.dealii.org/.
• 6: Brenner, S. C. and Scott, L. R. 1994. The Mathematical Theory of Finite Element Methods. Springer-Verlag.
• 7: Ciarlet, P. G. 1976. Numerical Analysis of the Finite Element Method. Les Presses de l'Universite de Montreal.
• 8: Dular, P. and Geuzaine, C. 2006. GetDP: a General environment for the treatment of Discrete Problems. http://www.geuz.org/getdp/.
• 9: K. Eriksson , D. Estep , P. Hansbo , C. Johnson, Computational Differential Equations, Press Syndicate of the University of Cambridge, 1996
• 10: Eriksson, K., Estep, D., and Johnson, C. 2003. Applied Mathematics: Body and Soul. Vol. III. Springer-Verlag.
• 11: Hoffman, J., Jansson, J., Johnson, C., Knepley, M. G., Kirby, R. C., Logg, A., Scott, L. R., and Wells, G. N. 2006. FEniCS. http://www.fenics.org/.
• 12: Hoffman, J., Jansson, J., Logg, A., and Wells, G. N. 2006. DOLFIN. http://www.fenics.org/dolfin/.
• 13: Hoffman, J. and Johnson, C. 2004. Encyclopedia of Computational Mechanics, Volume 3 (Chapter 7, Computability and Adaptivity in CFD). John Wiley.
• 14: Hughes, T. J. R. 1987. The Finite Element Method: Linear Static and Dynamic Finite Element Analysis. Prentice-Hall.
• 15: Karniadakis, G. E. and Sherwin, S. J. 1999. Spectral/Hp Element Methods for CFD. Numerical Mathematics and Scientific Computation. Oxford University Press, New York.
• 16: 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]
• 17: Kirby, R. C. 2006a. FIAT. http://www.fenics.org/fiat/.
• 18: 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]
• 19: 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]
• 20: Kirby, R. C., Knepley, M. G., and Scott, L. R. 2004. Evaluation of the action of finite element operators. Tech. rep. TR--2004--07, University of Chicago, Department of Computer Science.
• 21: 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]
• 22: Robert C. Kirby , Anders Logg , L. Ridgway Scott , Andy R. Terrel, Topological Optimization of the Evaluation of Finite Element Matrices, SIAM Journal on Scientific Computing, v.28 n.1, p.224-240, 2006 [doi>10.1137/050635547]
• 23: Hans Petter Langtangen , D. Keyes , R. Nieminen , M. Griebel , M. Griebel Bonn , T. Schlick , D. Roose, Computational Partial Differential Equations: Numerical Methods and Diffpack Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 24: Logg, A. 2004. Automation of computational mathematical modeling. Ph.D. thesis, Chalmers University of Technology, Sweden.
• 25: Logg, A. 2006. FFC. http://www.fenics.org/ffc/.
• 26: 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.
• 27: Oliphant, T. et al. 2006. Python Numeric. URL: http://numeric.scipy.org/.
• 28: Pironneau, O., Hecht, F., Hyaric, A. L., and Ohtsuka, K. 2006. FreeFEM. http://www.freefem.org/.

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:
BLAS, automation, compiler, finite element, granularity, loop hoisting, monomials, variational form