Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics
The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-09-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/12/9/187 |
| _version_ | 1811198243817652224 |
|---|---|
| author | Hristo N. Djidjev Georg Hahn Susan M. Mniszewski Christian F. A. Negre Anders M. N. Niklasson |
| author_facet | Hristo N. Djidjev Georg Hahn Susan M. Mniszewski Christian F. A. Negre Anders M. N. Niklasson |
| author_sort | Hristo N. Djidjev |
| collection | DOAJ |
| description | The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have been published in the literature for such simulations. We aim to use a special type of graph partitioning to efficiently parallelize these computations. For this, we create a graph representing the zero−nonzero structure of a thresholded density matrix, and partition that graph into several components. Each separate submatrix (corresponding to each subgraph) is then substituted into the matrix polynomial, and the result for the full matrix polynomial is reassembled at the end from the individual polynomials. This paper starts by introducing a rigorous definition as well as a mathematical justification of this partitioning problem. We assess the performance of several methods to compute graph partitions with respect to both the quality of the partitioning and their runtime. |
| first_indexed | 2024-04-12T01:27:36Z |
| format | Article |
| id | doaj.art-adfbab3c0a7f439387119a1bb334f177 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-12T01:27:36Z |
| publishDate | 2019-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-adfbab3c0a7f439387119a1bb334f1772022-12-22T03:53:34ZengMDPI AGAlgorithms1999-48932019-09-0112918710.3390/a12090187a12090187Using Graph Partitioning for Scalable Distributed Quantum Molecular DynamicsHristo N. Djidjev0Georg Hahn1Susan M. Mniszewski2Christian F. A. Negre3Anders M. N. Niklasson4Los Alamos National Laboratory, Los Alamos, NM 87544, USADepartment of Mathematics and Statistics, Lancaster University, Bailrigg, Lancaster LA1 4YW, UKLos Alamos National Laboratory, Los Alamos, NM 87544, USALos Alamos National Laboratory, Los Alamos, NM 87544, USALos Alamos National Laboratory, Los Alamos, NM 87544, USAThe simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have been published in the literature for such simulations. We aim to use a special type of graph partitioning to efficiently parallelize these computations. For this, we create a graph representing the zero−nonzero structure of a thresholded density matrix, and partition that graph into several components. Each separate submatrix (corresponding to each subgraph) is then substituted into the matrix polynomial, and the result for the full matrix polynomial is reassembled at the end from the individual polynomials. This paper starts by introducing a rigorous definition as well as a mathematical justification of this partitioning problem. We assess the performance of several methods to compute graph partitions with respect to both the quality of the partitioning and their runtime.https://www.mdpi.com/1999-4893/12/9/187density matrixG-SP2graph partitioningmolecular dynamicsQMDSP2 algorithm |
| spellingShingle | Hristo N. Djidjev Georg Hahn Susan M. Mniszewski Christian F. A. Negre Anders M. N. Niklasson Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics Algorithms density matrix G-SP2 graph partitioning molecular dynamics QMD SP2 algorithm |
| title | Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics |
| title_full | Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics |
| title_fullStr | Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics |
| title_full_unstemmed | Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics |
| title_short | Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics |
| title_sort | using graph partitioning for scalable distributed quantum molecular dynamics |
| topic | density matrix G-SP2 graph partitioning molecular dynamics QMD SP2 algorithm |
| url | https://www.mdpi.com/1999-4893/12/9/187 |
| work_keys_str_mv | AT hristondjidjev usinggraphpartitioningforscalabledistributedquantummoleculardynamics AT georghahn usinggraphpartitioningforscalabledistributedquantummoleculardynamics AT susanmmniszewski usinggraphpartitioningforscalabledistributedquantummoleculardynamics AT christianfanegre usinggraphpartitioningforscalabledistributedquantummoleculardynamics AT andersmnniklasson usinggraphpartitioningforscalabledistributedquantummoleculardynamics |