# Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
## 2 Evaluating Matrix Polynomials on Partitions  
We define a thresholded matrix polynomial, justify its parallelized evaluation, present an algorithm to evaluate a matrix polynomial in a parallelized fashion, and conclude by defining the cost function for an implied graph partitioning problem. We encode the zero-nonzero structure of a symmetric matrix \(X=\{x_{ij}\}\) as a graph \(G(X)\), called the _sparsity graph_ of \(X\). \(G(X)\) contains a vertex for each row (or column) in \(X\), and \(G(X)\) contains an edge between vertices \(i\) and \(j\) if and only if \(x_{ij}\
eq 0\). We now generalize the matrix polynomial defined in (1) for any symmetric \(n\times n\) matrix \(A\). Denote the superposition of operators of the type  
\[P=P_{1}\circ T_{1}\circ\ldots\circ P_{s}\circ T_{s} \tag{2}\]  
as a _thresholded matrix polynomial_ of degree \(2^{s}\), where \(T_{i}\) is a thresholding operation and \(P_{i}\) is a polynomial of degree \(2\). For any graph \(I\), we formally define \(T_{i}\) as the graph operator (with associated edge set \(E(T_{i})\)) such that \(T_{i}(I)\) is a graph with a vertex set \(V(I)\) and an edge set \(E(I)\setminus E(T_{i})\). The application of a superpositioned operator \(P\) of the type (2) to a matrix \(A\) of appropriate dimension is denoted as \(P(A)\). In (2), \(P\) is composed of polynomials \(P_{i}\) and thresholding operations \(T_{i}\). For our SM-SP2 application, the Hamiltonian is \(A\) and the density matrix is \(P(A)\). For any matrix \(A\), we define all matrices \(B\) which have the same zero-nonzero structure as \(A\) (that is, \(G(A)=G(B)\)) to be in the structure class \(\mathcal{M}(A)\). We observe that the nonzero structure of \(P(A)\) and \(P(B)\) can be different. Let \(G=G(A)\) for a matrix \(A\) and let \(P\) be a thresholded matrix polynomial. We denote by \(\mathcal{P}(G)\) the minimal graph with the same vertices as \(G\) such that if \(P(B)|_{vw}\
eq 0\) for any matrix \(B\in\mathcal{M}(A)\) and any \(v,w\), then there is an edge \((v,w)\in E(\mathcal{P}(G))\). We interpret \(\mathcal{P}(G)\) as the worst-case zero-nonzero structure of \(P(A)\) that excludes cancellations resulting from the addition of opposite-sign numbers, thus resulting in coincidental zeros. All diagonal elements of \(A\) are assumed to be nonzero, and \(E(T_{i})\) is assumed to not contain a loop edge. Assume we are given a set \(\Pi=\{\Pi_{1},\ldots,\Pi_{q}\}\), where each \(\Pi_{i}=U_{i}\cup W_{i}\), called a _block_ of \(\Pi\), is a union of a _core_ vertex set \(U_{i}\) and a _halo_ vertex set \(W_{i}\). Given the two following conditions hold true, we call \(\Pi\) a _CH-partition_ (or core-halo partition):  
1. \(\bigcup_{i}U_{i}=V(G),\ U_{i}\cap U_{j}=\emptyset\) for all \(i\
eq j\);
2. neighbors of vertices in \(U_{i}\) that are themselves not in \(U_{i}\) are contained in \(W_{i}\). Let \(H_{U_{i}}\) be the subgraph of \(H=\mathcal{P}(G)\) induced by all neighbors of \(U_{i}\) in \(H\). We combine all rows and columns of \(A\) that correspond to vertices of \(V(H_{U_{i}})\) in a submatrix \(A_{U_{i}}\) of \(A\). The following lemma shows that \(P(A)\) can be computed on submatrices of the Hamiltonian. Lemma 1: _For any \(v\in U_{i}\) and any neighbor \(w\) of \(v\) in \(\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(A_{U_{i}})\) corresponding to the edge \((v,w)\) of \(H_{i}\)._  
The proof is given in Appendix A. Lemma 1 justifies the parallelized evaluation of a matrix polynomial. Let us apply the aforementioned results to a Hamiltonian matrix \(A\) in a QMD simulation. (See the example in Figure 1). In this case, we can assume that the sparsity structure of the density matrix \(D\) from the previous QMD simulation step is being passed on to \(P(A)\). We can thus approximate \(H=\mathcal{P}(G)\) with \(G(D)\) since the graph \(H\) is unknown until \(P(A)\) is computed. This is a reasonable approximation since the connectivity will only change marginally from step to step in the QMD simulation.