# Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
## 1 Introduction
However, the significant communication overhead for every iteration causes SM-SP2 to not parallelize well. Linear scaling complexity has been achieved with thresholded blocked sparse-matrix algebra [5; 6; 7; 8]. In our paper, we present an alternative formulation that reduces communication overhead via graph partitioning and enables scalable parallelism. Our basic approach was introduced in [9], but with the main focus being on the physics aspects. This paper addresses the aforementioned parallel version of SP2 together with an inbuilt partitioning scheme applied to the graph representation of the density matrix, denoted as G-SP2 in the remainder of the article. In particular, the computational aspects of evaluating the matrix polynomial in G-SP2 are investigated. We represent the Hamiltonian (or density) matrix as a graph where atomic orbitals are given as vertices and nonzero interactions become edges, and then partition that graph into blocks (parts) with the aim to minimize a suitable cost function. The submatrices of the Hamiltonian or density matrix correspond to the divisions of the molecule, and are derived from the graph partitioning. We rigorously prove that applying the matrix polynomial to the entire Hamiltonian is equivalent to applying it to the partitioned Hamiltonian matrix and re-assembling the partial solutions, thus justifying our approach to parallelize the computational workload via graph partitioning. Although demonstrated numerically [9], no such proof exists in the literature to the best of our knowledge. Our algorithm is related to the general framework of [10] (specifically the case of overlapped subdomains), who present a general methodology to partition workloads among several processors. Their work is similar in that standard graph partitionings are considered, which are then locally modified to further optimize them (we attempt the same with a simulated annealing approach in Section 3.2). However, there are crucial differences to the work presented in this article: Since their framework is very general, it does not consider our specific objective function presented later in Section 2, their general algorithm works with a distance cutoff for modifying partitions which we do not recommend, and most importantly, we prove that for our problem, the partitioned matrix polynomial indeed allows lossless parallelization. We show that partitions with overlapping blocks (or _halos_) need to be computed to obtain accurate results with our graph approach. Naturally, the computational overhead increases with the overlap. The aim of this work is to minimize the computational cost of the matrix polynomial evaluation through appropriate partitioning schemes. Those schemes will directly minimize the cost of the corresponding polynomial evaluation as opposed to traditional edge cut minimization. In our article, we will experimentally study several algorithms for the aforementioned graph partitioning problem, which we formally introduce first. In [11], the authors consider a similar set-up in which the graph encoding the molecular structure is partitioned (using various techniques) for faster heuristic computation; however, their article crucially differs from ours in that there are no generally applicable results pertaining to lossless partitioning of the matrix polynomial using overlapping blocks. Our approach allows us to avoid communication between processors after each iteration of (1) until the entire polynomial is evaluated. To this end, each processor independently evaluates its assigned polynomial after partitioning and distributing the initial matrix, and the final output is assembled from the computed submatrices. In this article, different algorithmic approaches for computing graph partitions are assessed with respect to the aforementioned objective function and their computational effort. Importantly, we analyze the tradeoff between the additional computational costs for computing graph partitions before running the SP2 algorithm in parallel, and carrying out regular molecular dynamics.