# Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
## Appendix A Proofs for Section 2  
For any graph \(I\) and vertex \(v\in I\), the _neighborhood_ of \(v\) in \(I\) is the set \(N(v,I)=\{w\in V(I)\mid(v,w)\in E(I)\}\). Let \(H=\mathcal{P}(G)\), \(v\) be a vertex of \(G\), and \(H_{v}\) denote the subgraph of \(H\) induced by \(N(v,H)\). For thefollowing lemmas we assume that \(T_{i}\cap E(H)=\emptyset\) for all \(i\), i.e., none of the edges in \(H=\mathcal{P}(G)\) are thresholded. (With thresholding, the partitioned matrix algorithm is not exact, but approximate.) We have the following properties. Let \(v\) be a vertex of \(G\). Then \(N(v,\mathcal{P}(G))=N(v,\mathcal{P}(H_{v}))\). Proof. : First we prove that \(N(v,\mathcal{P}(G))\subseteq N(v,\mathcal{P}(H_{v}))\). Let \(w\in N(v,\mathcal{P}(G))\). Then \((v,w)\in E(\mathcal{P}(G))\) and hence \((v,w)\in E(H_{v})\subseteq E(H)\). Since by assumption \(T_{i}\cap E(H)=\emptyset\), \((v,w)\
ot\in T_{i}\) for all \(i\). From \((v,w)\in E(H_{v})\), the last relation, and the fact that all vertices of \(H\) have loops, \((v,w)\in E(\mathcal{P}(H_{v}))\). Hence, \(w\in N(v,\mathcal{P}(H_{v}))\). Now we prove that \(N(v,\mathcal{P}(H_{v}))\subseteq N(v,\mathcal{P}(G))\). Let \(w\in N(v,\mathcal{P}(H_{v}))\). Since \(\mathcal{P}(H_{v})\) and \(H_{v}\) have the same vertex sets, we have \(w\in N(v,H_{v})\). Furthermore, since \(H_{v}\) is a subgraph of \(H\), \(w\in N(v,H)=N(v,\mathcal{P}(G))\). The lemma shows that \(v\) has the same neighbors in \(\mathcal{P}(G)\) and \(\mathcal{P}(H_{v})\), i.e., their corresponding matrices have nonzero entries in the same positions in the row (or column) corresponding to \(v\). We will next strengthen that claim by showing that the corresponding nonzero entries contain equal values. Let \(X_{v}\) be the submatrix of \(A\) defined by all rows and columns that correspond to vertices of \(V(H_{v})\). We will call vertex \(v\) the _core_ and the remaining vertices the _halo_ of \(V(H_{v})\). We define the set \(\{V(H_{v})\mid v\in G\}\) to be the _CH-partition_ of \(G\). Please note that unlike other definitions of a partition used elsewhere, the vertex sets of CH-partitions (and, specifically, the halos) can be, and typically are, overlapping. For any \(v\in V(G)\) and any \(w\in N(v,\mathcal{P}(G))\), the element of \(P(A)\) corresponding to the edge \((v,w)\) of \(\mathcal{P}(G)\) is equal to the element of \(P(X_{v})\) corresponding to the edge \((v,w)\) of \(\mathcal{P}(H_{v})\). Proof. : Let \(2^{s}\) be the degree of \(P\). We will prove the lemma by induction on \(s\). Clearly, the claim is true for \(s=0\) since the elements of both \(A^{1}\) and \(X^{1}\) are original elements of the matrix \(A\). Assume the claim is true for \(s-1\). Define \(P^{\prime}=P_{1}\circ_{1}\circ_{\ldots}\circ_{P_{s-1}}\circ_{T_{s-1}}\). By the inductive assumption, the corresponding elements in the matrices \(A^{\prime}=P^{\prime}(A)\) and \(X^{\prime}=P^{\prime}(X)\) have equal values. We need to prove the same for the elements of \(A^{\prime 2}\) and \(X^{\prime 2}\). Let \((v,w)\in E(\mathcal{P}(G))\). By Lemma A, \((v,w)\in E(\mathcal{P}(H_{v}))\). For each vertex \(u\) of \(\mathcal{P}(H_{v})\) let \(u^{\prime}\) denote the corresponding row/column of \(X\). We want to show that \(P(A)(v,w)=P(X)(v^{\prime},w^{\prime})\). By definition of matrix product, \(A^{\prime 2}(v,w)=\sum A^{\prime}(v,u)A^{\prime}(u,w)\), where the summation is over all \(u\) such that \((v,u),(u,w)\in E(\mathcal{P}(G))\). Similarly, \(X^{\prime 2}(v^{\prime},w^{\prime})=\sum X^{\prime}(v^{\prime},u^{\prime})X^{ \prime}(u^{\prime},w^{\prime})\), where the summation is over the values of \(u^{\prime}\) corresponding to the values of \(u\) from the previous formula, by Lemma A. By the inductive assumption, \(A^{\prime}(v,u)=X^{\prime}(v^{\prime},u^{\prime})\) and \(A^{\prime}(u,w)=X^{\prime}(u^{\prime},w^{\prime})\), thus \(A^{\prime 2}(v,w)=X^{\prime 2}(v^{\prime},w^{\prime})\).