La simulación del movimiento físico de sistemas de múltiples cuerpos a nivel atomístico, con fuerzas calculadas a partir de una descripción cuántica de los electrones, motiva un problema de particionamiento de gráficos estudiado en este artículo. Varios algoritmos avanzados que se basan en evaluaciones de polinomios de matrices han sido publicados en la literatura para tales simulaciones. Nuestro objetivo es utilizar un tipo especial de particionamiento de gráficos para paralelizar eficientemente estos cálculos. Para ello, creamos un gráfico que representa la estructura de ceros-no ceros de una matriz de densidad umbralada, y dividimos ese gráfico en varios componentes. Cada submatriz separada (correspondiente a cada subgrafo) se sustituye luego en el polinomio de matriz, y el resultado del polinomio de matriz completo se reensambla al final a partir de los polinomios individuales. Este artículo comienza presentando una definición rigurosa y una justificación matemática de este problema de particionamiento. Evaluamos el rendimiento de varios métodos para calcular particiones de gráficos con respecto tanto a la calidad de la partición como a su tiempo de ejecución.