Geometric Separators for Finite-Element Meshes

Abstract

We propose a class of graphs that would occur naturally in finite-element and finite-difference problems and we prove a bound on separators for this class of graphs. Graphs in this class are embedded in $d$-dimensional space in a certain manner. For d-dimensional graphs our separator bound is O(n(d-1)d), which is the best possible bound. We also propose a simple randomized algorithm to find this separator in O(n) time. This separator algorithm can be used to partition the mesh among processors of a parallel computer and can also be used for the nested dissection sparse elimination algorithm.