Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Graph Partitioning Methods for Fast Parallel Quantum Molecular Dynamics
AU - Djidjev, Hristo N.
AU - Hahn, Georg
AU - Mniszewski, Susan M.
AU - Negre, Christian F. A.
AU - Niklasson, Anders M. N.
AU - Sardeshmukh, Vivek B.
PY - 2016/10/10
Y1 - 2016/10/10
N2 - We study a graph partitioning problem motivated by the simulation of the physical movement of multi-body systems on an atomistic level, where the forces are calculated from a quantum mechanical description of the electrons. Several advanced algorithms have been published in the literature for such simulations that are based on evaluations of matrix polynomials. We aim at efficiently parallelizing these computations by using a special type of graph partitioning. For this, we represent the zero-nonzero structure of a thresholded matrix as a graph and partition that graph into several components. The matrix polynomial is then evaluated for each separate submatrix corresponding to the subgraphs and the evaluated submatrix polynomials are used to assemble the final result for the full matrix polynomial. The paper provides a rigorous definition as well as a mathematical justification of this partitioning problem. We use several algorithms to compute graph partitions and experimentally evaluate their performance with respect to the quality of the partition obtained with each method and the time needed to produce it.
AB - We study a graph partitioning problem motivated by the simulation of the physical movement of multi-body systems on an atomistic level, where the forces are calculated from a quantum mechanical description of the electrons. Several advanced algorithms have been published in the literature for such simulations that are based on evaluations of matrix polynomials. We aim at efficiently parallelizing these computations by using a special type of graph partitioning. For this, we represent the zero-nonzero structure of a thresholded matrix as a graph and partition that graph into several components. The matrix polynomial is then evaluated for each separate submatrix corresponding to the subgraphs and the evaluated submatrix polynomials are used to assemble the final result for the full matrix polynomial. The paper provides a rigorous definition as well as a mathematical justification of this partitioning problem. We use several algorithms to compute graph partitions and experimentally evaluate their performance with respect to the quality of the partition obtained with each method and the time needed to produce it.
KW - quant-ph
U2 - 10.1137/1.9781611974690.ch5
DO - 10.1137/1.9781611974690.ch5
M3 - Conference contribution/Paper
SP - 42
EP - 51
BT - 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing
A2 - Gebremedhin, Assefaw H.
A2 - Boman, Erik G.
A2 - Ucar, Bora
PB - SIAM PUBLICATIONS
ER -