# Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
## 5 Discussion  
This paper speeds up the computation of the density matrix in MD simulations through parallelization, informed by graph partitioning applied to the structure graph underlying a molecule. Our experimental results are based on graphs derived from density matrices of physical systems. In our article we focus on a certain flavor of the classical graph partitioning problem arising from molecular dynamics simulations. In contrast to classical edge cut partitioning, we minimize blocks with respect to both the number of their core vertices and the number of their neighbors in adjacent blocks (halos). To the best of our knowledge, this type of graph partitioning (which we coin _CH-(core-halo)-partitioning_) has not been studied previously. This work makes two contributions. First, the CH-partitioning problem under consideration is mathematically described and justified. We prove that the partitioned evaluation of a matrix polynomial is equivalent to the evaluation of the original (unpartitioned) matrix given a sufficient condition is satisfied. Second, we evaluate several approaches for computing CH-partitions using three performance measures: the total computational effort, the maximal effort per processor, and the overall computational runtime. Special focus is given to the post-processing of partitions obtained with conventional graph partitioning algorithms for which we use our own modified SA approach. We find that our flavor of the partitioning problem can be solved using standard graph partitioning packages. Moreover, post-optimization of the partitions obtained through classical graph partitioning packages can be performed well with our SA scheme. As expected, the time to evaluate matrix polynomials for different system (graph) sizes decreases with both the number of processors and blocks in our simulations. Our main result is that the increased effort for graph partitioning and post-optimization with SA is beneficial overall when applying our parallelized version of the G-SP2 algorithm to meaningful physical systems. Based on our observation that _METIS_ with a SA post-processing step is significantly faster than competing methods while giving the best results on average, we recommend this combination for practical use. Of course, the research in this article can be always updated by including newer partitioning algorithms as time progresses, such as KaHyPar [23]. Additionally, a consideration of the statistical significance of our results could be of interest as future work. H.N.D. provided the mathematical theory on graph partitioning and all proofs. [PERSON] was responsible for writing the manuscript, as well as for conducting simulations. [PERSON] helped with all details related to the chemistry aspects of QMD in the paper, as well as with proof reading the manuscript. [PERSON] conducted some of the simulations, helped with the details related to the chemistry aspects of the paper, as well as with the preparation of the manuscript. [PERSON] helped with details related to the chemistry aspects of the paper, with writing the introduction, and with proof reading the manuscript. **Funding:** We acknowledge support from the Office of Basic Energy Sciences (LANL2014E8 AN) and the Laboratory Directed Research and Development program of Los Alamos National Laboratory. This research used resources provided by the Los Alamos National Laboratory Institutional Computing Program, which is supported by the U.S. Department of Energy National Nuclear Security Administration. This research has been supported at Los Alamos National Laboratory under the Department of Energy contract DE-AC52-06 NA25396. **Acknowledgments:** The authors would like to thank [PERSON] for his help with various aspects related to graph partitioning, [PERSON] and [PERSON] for their help with selecting meaningful physical datasets of real-world molecules, and [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], [PERSON], and [PERSON] for their feedback.