L. Ridgway Scott

Robert C. Kirby, Matthew Knepley, Anders Logg et al.

Assembling stiffness matrices represents a significant cost in many finite element computations. We address the question of optimizing the evaluation of these matrices. By finding redundant computations, we are able to significantly reduce the cost of building local stiffness matrices for the Laplace operator and for the trilinear form for Navier-Stokes. For the Laplace operator in two space dimensions, we have developed a heuristic graph algorithm that searches for such redundancies and generates code for computing the local stiffness matrices. Up to cubics, we are able to build the stiffness matrix on any triangle in less than one multiply-add pair per entry. Up to sixth degree, we can do it in less than about two. Preliminary low-degree results for Poisson and Navier-Stokes operators in three dimensions are also promising.

Robert C. Kirby, Anders Logg, L. Ridgway Scott et al.

We present a topological framework for finding low-flop algorithms for evaluating element stiffness matrices associated with multilinear forms for finite element methods posed over straight-sided affine domains. This framework relies on phrasing the computation on each element as the contraction of each 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.

Peter R. Brune, Matthew G. Knepley, L. Ridgway Scott

The use of multigrid and related preconditioners with the finite element method is often limited by the difficulty of applying the algorithm effectively to a problem, especially when the domain has a complex shape or adaptive refinement. We introduce a simplification of a general topologically-motivated mesh coarsening algorithm for use in creating hierarchies of meshes for geometric unstructured multigrid methods. The connections between the guarantees of this technique and the quality criteria necessary for multigrid methods for non-quasi-uniform problems are noted. The implementation details, in particular those related to coarsening, remeshing, and interpolation, are discussed. Computational tests on pathological test cases from adaptive finite element methods show the performance of the technique.

Patrick E. Farrell, Michael Neilan, Charles Parker et al.

We present new convergence estimates for the iterated penalty method applied to structure-preserving discretizations of linear generalized saddle point systems. The method may be viewed as an Uzawa iteration on an augmented Lagrangian formulation of the system. As a by-product, we obtain sharper stability estimates for penalized/perturbed saddle point problems. Three model finite element applications show agreement with the theory.

Andrei Draganescu, L. Ridgway Scott

We introduce a novel technique for proving global strong discrete maximum principles for finite element discretizations of linear and semilinear elliptic equations for cases when the common, matrix-based sufficient conditions are not satisfied. The basic argument consists of extending the strong form of discrete maximum principle from macroelements to the entire domain via a connectivity argument. The method is applied to discretizations of elliptic equations with certain pathological meshes, and to semilinear elliptic equations.