Optimizing FIAT with level 3 BLAS

ABSTRACT

Our previous work on FIAT (Finite Element Automatic Tabulator) developed a “computational representation theory ” that allowed us to construct arbitrary order instances of a wide range of finite elements, many of which are infrequently used owing to their associated code complexity. In our present work, we further hone this theory by rephrasing most of the internal operations as linear transformations over finite-dimensional Banach spaces. This additional insight has led to increased code granularity and allowed the use of level 3 BLAS operations. This is both a conceptual and a practical development; as the run-time performance of FIAT has been improved multiple orders of magnitude.

REFERENCES

• 1: Arnold, D. N. and Winther, R. 2002. Mixed finite elements for elasticity. Numer. Math. 92, 3, 401--419.
• 2: Paolo Bientinesi , John A. Gunnels , Margaret E. Myers , Enrique S. Quintana-Ortí , Robert A. van de Geijn, The science of deriving dense linear algebra algorithms, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.1-26, March 2005 [doi>10.1145/1055531.1055532]
• 3: Brenner, S. C. and Scott, L. R. 2002. The Mathematical Theory of Finite Element Methods, 2nd Ed. Springer-Verlag, Berlin, Germany.
• 4: 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.
• 5: Franco Brezzi , Michel Fortin, Mixed and hybrid finite element methods, Springer-Verlag New York, Inc., New York, NY, 1991
• 6: Philippe G. Ciarlet, Finite Element Method for Elliptic Problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002
• 7: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 8: Moshe Dubiner, Spectral methods on triangles and other domains, Journal of Scientific Computing, v.6 n.4, p.345-390, Dec. 1991 [doi>10.1007/BF01060030]
• 9: 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]
• 10: Knepley, M. and Karpeev, D. A flexible representation for computational meshes. in preparation.
• 11: Laboratory, A. N. Petsc 3 web page. http://www-unix.mcs.anl.gov/petsc/petsc-3/.
• 12: Logg, A. 2005. FFC: the FEniCS Form Compiler. http://www.fenics.org/ffc.
• 13: Long, K. 2003. Sundance, a rapid prototyping tool for parallel PDE-constrained optimization. In Proceedings of the Large-Scale PDE-Constrained Optimization. Lecture Notes in Computational Science and Engineering. Springer-Verlag, Berlin, Germany.
• 14: Raviart, P.-A. and Thomas, J. M. 1977. A mixed finite element method for 2nd order elliptic problems. In Mathematical Aspects of Finite Element Methods (Proceedings of the Conference, Consiglio of Nazionale delle Ricerche (C.N.R.), Rome, Italy, 1975) Lecture Notes in Mathematics, Vol. 606, Springer Verlag, Berlin, Germany, 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:
Finite element, Hilbert space, numerical linear algebra