# Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
## 4 Experiments
### Comparison of the Partitioning Algorithms  
Six methods are tested to partition each graph of Table 1 into 16 blocks:  
1. _METIS_ with parameters of Section 4.1;
2. _METIS_ with subsequent simulated annealing (SA);
3. _hMETIS_;
4. _hMETIS_ with subsequent SA; \begin{table}
\begin{tabular}{l r r r l} \hline \hline
**Name** & \multicolumn{1}{c}{\(n\)} & \multicolumn{1}{c}{\(m\)} & \multicolumn{1}{c}{\(m/n\)} & **Description** \\ \hline polyethylene dense crystal & 18,432 & 4,112,189 & 223.1 & crystal molecule in water solvent (low threshold) \\ polyethylene sparse crystal & 18,432 & 812,343 & 44.1 & crystal molecule in water solvent (high threshold) \\ phenyl dendrimer & 730 & 31,147 & 42.7 & polyphenylene branched molecule \\ polyalanine 189 & 31,941 & 1,879,751 & 58.9 & polyalanine protein solvated in water \\ peptide 1 aft & 385 & 1833 & 4.76 & ribonucleoside-diphosphate reductase protein \\ polyethylene chain 1024 & 12,288 & 290,816 & 23.7 & chain of polymer molecule, almost 1-dimensional \\ polyalanine 289 & 41,185 & 1,827,256 & 44.4 & large protein in water solvent \\ peptide trp cage & 16,863 & 176,300 & 10.5 & smallest protein with ability to fold (in water) \\ urea crystal & 3584 & 109,067 & 30.4 & organic compound in living organisms \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Physical systems of our study: Number of vertices \(n\) in the graph and number of edges \(m\). Table taken from [12]. Copyright ©2016 Society for Industrial and Applied Mathematics. Reprinted with permission. All rights reserved. Figure 3: Molecular systems of this study: polyethylene linear chain (**first plot**), urea crystal (**second plot**), 189 residue polyalanine solvated in a water box (**third plot**), and phenyl dendrimer molecule (**fourth plot**). Cyan, blue, red, and white spheres represent carbon, nitrogen, oxygen, and hydrogen atoms, respectively. Figure taken from [12]. Copyright ©2016 Society for Industrial and Applied Mathematics. Reprinted with permission. All rights reserved. * _KaHIP_;
* _KaHIP_ with subsequent SA. As before, the sum of cubes (3) criterion is used to assess the effectiveness of each method. Figures 4 and 5 show experimental results. We observe that all algorithms perform well (except for the first two systems), and that _METIS_ and _KaHIP_ are significantly faster than _lMETIS_. Importantly, post-processing with SA seems to improve solutions in almost all cases at negligible additional runtime, and is thus recommended. Surprisingly, CH-partitions seem to pose a challenge for _hMETIS_ as its solutions are usually worse than those of the other two methods, and its runtime significantly exceeds the one of the other methods (an explanation of this remains for further research). We conclude that for these two reasons, _hMETIS_ seems unsuited for QMD simulations over longer time intervals, which is the aim of this work. Although solutions returned by _KaHIP_ are of very good quality (measured with the sum of cubes criterion), the combination of _METIS_ and SA still outperforms _KaHIP_ while also having a shorter combined runtime. The behavior of our algorithms seems to be dependent on the sparsity of the graph of a physical system. First, _METIS_ can outperform _hMETIS_ for denser graphs, but not for sparser ones. Second, the post-improvement of partitions with SA seems to be especially effective for dense graphs, which can be explained with the fact that dense graphs offer more possibilities to reassign and optimize edges than sparse graphs. This can be seen when applying the combination of _METIS+SA_ to the dense dendrimer system, see ([12], Table 2) for details. Figure 6 visualizes the relationship between the graph structure of a molecule (for the phenyl dendrimer molecule of Table 1) and its graph partitioning obtained through _METIS_ and SA. After partitioning the molecular graph structure, the fractal-like structure of the phenyl dendrimer molecule and its dense components become clearly visible, as well as its sparse connections to other dense components.