Partitioning of domains embedded in a regular grid

Abstract

In this thesis we present a partitioning algorithm aimed at partitioning domains embedded in a regular grid. Inspired by the multilevel philosophy of the Mondriaan algorithm, we manage to improve Mondriaan’s run time up to a factor of approximately 2 for certain test cases, while also constructing a better quality partitioning. While we significantly optimize both the coarsening and the initial partitioning phase of said multilevel method, we do not see comparable improvements in the uncoarsening phase. This means that the overhead of the general partitioner Mondriaan for a grid-embedded domain is limited.