Discrete optimization of finite element matrix evaluation

The tensor contraction structure for the computation of the element tensor AT obtained in Chapter 8, enables not only the construction of a compiler for variational forms, but an optimizing compiler. For typical variational forms, the reference tensor A0 has significant structure that allows the element tensor AT to be computed on an arbitrary cell T at a lower computational cost. Reducing the number of operations by making use of this structure, leads naturally to several problems in discrete mathematics. This chapter introduces some of the optimizations that are possible, and discusses compile-time combinatorial optimization problems that form the core of the FErari project (Kirby et al., 2006; Kirby and Scott, 2007; Kirby and Logg, 2008), which is the subject of Chapter 12. We consider two basic kinds of optimizations in this chapter. First, we consider relations between pairs of rows in the reference tensor. This naturally leads to a graph that models proximity among these pairs. If two rows are “close” together, then one may reuse results computed with the first row to compute a desired quantity with the second. The proximity of two such rows is computed using a Hamming distance and linearity relations. This approach gives rise to a weighted graph that is (almost) a metric space, so we designate such optimizations as “topological”. Second, we consider relations between more than two rows of the reference tensor. Such relations typically rely on sets of rows, considered as vectors in Euclidean space. Because we are using planes and hyperplanes to reduce the amount of computation, we describe these optimizations as “geometric”. For comparison, we briefly discuss optimizations using more traditional optimized dense linear algebra packages.