{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:31:42Z","timestamp":1762867902786,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T00:00:00Z","timestamp":1567814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["20140074DR","20180267ER"],"award-info":[{"award-number":["20140074DR","20180267ER"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2013nonzero 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.<\/jats:p>","DOI":"10.3390\/a12090187","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T04:12:40Z","timestamp":1568002360000},"page":"187","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9286-8824","authenticated-orcid":false,"given":"Hristo N.","family":"Djidjev","sequence":"first","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos, NM 87544, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6008-2720","authenticated-orcid":false,"given":"Georg","family":"Hahn","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Lancaster University, Bailrigg, Lancaster LA1 4YW, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0077-0537","authenticated-orcid":false,"given":"Susan M.","family":"Mniszewski","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos, NM 87544, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian F. A.","family":"Negre","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos, NM 87544, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anders M. N.","family":"Niklasson","sequence":"additional","affiliation":[{"name":"Los Alamos National Laboratory, Los Alamos, NM 87544, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"7260","DOI":"10.1103\/PhysRevB.58.7260","article-title":"Self-consistent-charge density-functional tight-binding method for simulations of complex materials properties","volume":"58","author":"Elstner","year":"1998","journal-title":"Phys. Rev. B"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"5149","DOI":"10.1103\/PhysRevLett.81.5149","article-title":"Crystal structures of zirconia from first principles and self-consistent tight binding","volume":"81","author":"Finnis","year":"1998","journal-title":"Phys. Rev. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/(SICI)1521-3951(200001)217:1<41::AID-PSSB41>3.0.CO;2-V","article-title":"A self-consistent charge density-functional based tight-binding method for predictive materials simulations in physics, chemistry and biology","volume":"217","author":"Frauenheim","year":"2000","journal-title":"Phys. Stat. Sol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"155115","DOI":"10.1103\/PhysRevB.66.155115","article-title":"Expansion algorithm for the density matrix","volume":"66","author":"Niklasson","year":"2002","journal-title":"Phys. Rev. B"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"4644","DOI":"10.1021\/acs.jctc.5b00552","article-title":"Efficient parallel linear scaling construction of the density matrix for Born-Oppenheimer molecular dynamics","volume":"11","author":"Mniszewski","year":"2015","journal-title":"J. Chem. Theory Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"C72","DOI":"10.1137\/120870761","article-title":"An Optimized Sparse Approximate Matrix Multiply for Matrices with Decay","volume":"35","author":"Bock","year":"2013","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.parco.2014.03.012","article-title":"Sparse matrix multiplication: The distributed block-compressed sparse row library","volume":"40","author":"Borstnik","year":"2014","journal-title":"Parallel Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3565","DOI":"10.1021\/ct200897x","article-title":"Linear Scaling Self-Consistent Field Calculations with Millions of Atoms in the Condensed Phase","volume":"8","author":"VandeVondele","year":"2012","journal-title":"J. Chem. Theory Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"234101","DOI":"10.1063\/1.4952650","article-title":"Graph-based linear scaling electronic structure theory","volume":"144","author":"Niklasson","year":"2016","journal-title":"J. Chem. Phys."},{"key":"ref_10","unstructured":"P\u0131nar, A., and Hendrickson, B. (2001, January 23\u201327). Partitioning for Complex Objectives. Proceedings of the 15th International Parallel and Distributed Processing Symposium (CDROM), San Francisco, CA, USA."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Von Looz, M., Wolter, M., Jacob, C.R., and Meyerhenke, H. (2016). Better partitions of protein graphs for subsystem quantum chemistry. arXiv, 1\u201320.","DOI":"10.1007\/978-3-319-38851-9_24"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Djidjev, H.N., Hahn, G., Mniszewski, S.M., Negre, C.F., Niklasson, A.M., and Sardeshmukh, V. (2016, January 10\u201312). Graph Partitioning Methods for Fast Parallel Quantum Molecular Dynamics (full text with appendix). Proceedings of the SIAM Workshop on Combinatorial Scientific Computing (CSC16), Albuquerque, NM, USA.","DOI":"10.2172\/1330079"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., and Wagner, D. (2013). Graph Partitioning and Graph Clustering\u201410th DIMACS Implementation Challenge Workshop. Contemp. Math., 588.","DOI":"10.1090\/conm\/588"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs","volume":"20","author":"Karypis","year":"1999","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Fiduccia, C., and Mattheyses, R. (1982, January 14\u201316). A linear time heuristic for improving network partitions. Proceedings of the 19th IEEE Design Automation Conference, Las Vegas, NV, USA.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/978-3-642-38527-8_16","article-title":"Think Locally, Act Globally: Highly Balanced Graph Partitioning","volume":"Volume 7933","author":"Sanders","year":"2013","journal-title":"Proceedings of the International Symposium on Experimental Algorithms (SEA)"},{"key":"ref_17","first-page":"469","article-title":"Engineering multilevel graph partitioning algorithms","volume":"6942","author":"Sanders","year":"2011","journal-title":"LNCS"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford","year":"1956","journal-title":"Canad. J. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1155\/2000\/19436","article-title":"Multilevel k-way Hypergraph Partitioning","volume":"11","author":"Karypis","year":"2000","journal-title":"VLSI Des."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"200","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_21","unstructured":"Karypis, G., and Kumar, V. (2019, September 07). A Hypergraph Partitioning Package. Available online: http:\/\/glaros.dtc.umn.edu\/gkhome\/fetch\/sw\/hmetis\/manual.pdf."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1039\/TF9393500482","article-title":"The crystal structure of long-chain normal paraffin hydrocarbons. The \u201cshape\u201d of the CH2 group","volume":"35","author":"Bunn","year":"1939","journal-title":"Trans. Faraday Soc."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Schlag, S., Henne, V., Heuer, T., Meyerhenke, H., Sanders, P., and Schulz, C. (2015). k-way Hypergraph Partitioning via n-Level Recursive Bisection. arXiv, 1\u201321.","DOI":"10.1137\/1.9781611974317.5"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/187\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:17:37Z","timestamp":1760188657000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,7]]},"references-count":23,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["a12090187"],"URL":"https:\/\/doi.org\/10.3390\/a12090187","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,9,7]]}}}