Topological optimization of the evaluation of finite element matrices

Robert C. Kirby; Anders Logg; L. Ridgway Scott; Andy Terrel. 8 July, 2005.
Communicated by Robert Kirby.


We present a topological framework for finding low-flop algorithms for evaluating element stiffness matrices associated with multilinear forms for finite element methods. This framework relies on phrasing the computation on each element as the contraction of each of collection of reference element tensors with an element-specific geometric tensor. We then present a new concept of complexity-reducing relations} that serve as distance relations between these reference element tensors. This notion sets up a graph-theoretic context in which we may find an optimized algorithm by computing a minimum spanning tree. We present experimental results for some common multilinear forms showing significant reductions in operation count and also discuss some efficient algorithms for building the graph we use for the optimization.

Original Document

The original document is available in PDF (uploaded 8 July, 2005 by Robert Kirby).