  We study a graph partitioning problem motivated by the simulation of the
physical movement of multi-body systems on an atomistic level, where the forces
are calculated from a quantum mechanical description of the electrons. Several
advanced algorithms have been published in the literature for such simulations
that are based on evaluations of matrix polynomials. We aim at efficiently
parallelizing these computations by using a special type of graph partitioning.
For this, we represent the zero-nonzero structure of a thresholded matrix as a
graph and partition that graph into several components. The matrix polynomial
is then evaluated for each separate submatrix corresponding to the subgraphs
and the evaluated submatrix polynomials are used to assemble the final result
for the full matrix polynomial. The paper provides a rigorous definition as
well as a mathematical justification of this partitioning problem. We use
several algorithms to compute graph partitions and experimentally evaluate
their performance with respect to the quality of the partition obtained with
each method and the time needed to produce it.
