Automatic Domain Partitioning in Three Dimensions

The problem of automatically decomposing a mesh contained in a three-dimensional domain into p pieces is considered. This problem arises in the context of domain-decomposition solvers for partial differential equations (PDEs). Finite-difference meshes are considered, and a class of graphs that would naturally arise from a finite-element mesh in three dimensions is introduced. A general separation algorithm that matches a lower bound is given for this class. An algorithm satisfying better bounds in the case that the domain is a union of boxes is also given. The proposed algorithms are intended to subdivide the region efficiently as a preprocessing step for the parallel numerical solution of the PDE.