# Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
## 3 Algorithms for Graph Partitioning Considered in Our Study
### Refinement with Simulated Annealing  
The objective function (3) we aim to minimize differs from the size of the edge or hyperedge cut minimized by standard graph and hypergraph partitioning algorithms. With the help of the algorithm derived in this section we explicitly minimize (3). A standard tool in optimization is the probabilistic algorithm of [20], called simulated annealing (\(SA\)). SA iteratively proposes random modifications to an existing solution to improve it, and thus optimizes without gradients. If a proposed modification (or move) does not immediately lower the objective function, it might still be accepted with a certain _acceptance probability_. The acceptance probability is proportional to the magnitude of the (unfavorable) increase in the objective function, and antiproportional to the runtime. The latter makes it more likely for SA to accept unfavorable moves in the exploration phase at the start of each run, and it is implemented using a strictly decreasing _temperature_ function. Modifications to the existing solution which further minimize the objective function are always accepted. A fixed number of iterations, a vanishingly small temperature, or the lack of further improvements in the solution over a certain number of iterations can be employed as stopping criteria for SA. We test the following proposal functions that return modifications to subgraphs induced by an existing block of the partition, where \(P\) and \(P^{\prime}\) are simply sets of nodes:  
1. Select a random block \(P^{\prime}\), select one of its halo nodes \(v\) at random and move \(v\) into block \(P\). 2. Select a random block \(P^{\prime}\), select one of its nodes \(v\) at random and move \(v\) into \(P\). 3. Select the block \(P^{\prime}\) with most halo nodes and (a) move a random node \(v\) into \(P\), (b) make a random halo node of \(P\) a core node, or (c) move any node of \(P\) to another block. 4. Like (3.) using the block \(P^{\prime}\) with the largest sum of core and halo nodes. Many more sensible proposal functions could be devised. However, in our experiments we observed that the above proposals result in a similar behavior of SA, with the best tradeoff between speed and performance being achieved by scheme (1.). Algorithm 1 states the SA implementation we use in our experiments. Any regular (edge cut) partitioning (e.g., obtained with _METIS_), and even a random partitioning, serves as input \(\Pi\) (the set of blocks) to Algorithm 1. The SA algorithm runs over a fixed number of \(N\) iterations. In each iteration, we randomly select a block \(\pi\in\Pi\) as well as a random edge joining a core vertex \(v\) with a halo vertex \(w\) in \(\pi\). Afterwards, \(\pi\) is updated with \(w\) being a core vertex. After storing the new partitioning in a set \(\Pi^{\prime}\), both \(\Pi\) and \(\Pi^{\prime}\) are assessed. For this we compute the change \(\Delta\) in the objective function (3) between \(\Pi^{\prime}\) and \(\Pi\), which is used to update the acceptance probability \(p\). We accept \(\Pi^{\prime}\) (thus overwriting \(\Pi:=\Pi^{\prime}\)) with probability \(p\). Note that \(p>1\) if \(\Delta<0\), thus leading to a guaranteed acceptance of a proposal that directly improves (3). Afterwards, the iteration is repeated. ```
Input: Graph G, number of iterations \(N\), initial partitioning \(\Pi\) Output: Updated partitioning \(\Pi\)
1 Select a temperature function \(t(i)=1/i\) ;
2 for\(i=1\) to \(N\)do
3 Select random block \(\pi\) in \(\Pi\) and a random core-halo edge \((v,w)\) in \(\pi\);
4 Make \(w\) a core vertex of \(\pi\) and update the halo of \(\pi\);
5 Compute the values \(S\) and \(S^{\prime}\) of (3) for \(\Pi\) and \(\Pi^{\prime}\), respectively, and set \(\Delta=S^{\prime}-S\);
6 Compute \(p=\exp{(-\Delta/t(i))}\);
7 Set \(\Pi=\Pi^{\prime}\) with probability \(\min(1,p)\);
8 Output partitioning \(\Pi\);
```  
**Algorithm 1**Simulated Annealing. SA is run with a maximal number of iterations \(N=100\) as stopping criterion, and the temperature function is chosen as \(t(i)=1/i\).