  The simulation of the physical movement of multi-body systems at an atomistic
level, with forces calculated from a quantum mechanical description of the
electrons, motivates a graph partitioning problem studied in this article.
Several advanced algorithms relying on evaluations of matrix polynomials have
been published in the literature for such simulations. We aim to use a special
type of graph partitioning in order to efficiently parallelize these
computations. For this, we create a graph representing the zero-nonzero
structure of a thresholded density matrix, and partition that graph into
several components. Each separate submatrix (corresponding to each subgraph) is
then substituted into the matrix polynomial, and the result for the full matrix
polynomial is reassembled at the end from the individual polynomials. This
paper starts by introducing a rigorous definition as well as a mathematical
justification of this partitioning problem. We assess the performance of
several methods to compute graph partitions with respect to both the quality of
the partitioning and their runtime.
