{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:20:17Z","timestamp":1764937217366,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T00:00:00Z","timestamp":1602806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>The central importance of large-scale eigenvalue problems in scientific computation necessitates the development of massively parallel algorithms for their solution. Recent advances in dense numerical linear algebra have enabled the routine treatment of eigenvalue problems with dimensions on the order of hundreds of thousands on the world\u2019s largest supercomputers. In cases where dense treatments are not feasible, Krylov subspace methods offer an attractive alternative due to the fact that they do not require storage of the problem matrices. However, demonstration of scalability of either of these classes of eigenvalue algorithms on computing architectures capable of expressing massive parallelism is non-trivial due to communication requirements and serial bottlenecks, respectively. In this work, we introduce the SISLICE method: a parallel shift-invert algorithm for the solution of the symmetric self-consistent field (SCF) eigenvalue problem. The SISLICE method drastically reduces the communication requirement of current parallel shift-invert eigenvalue algorithms through various shift selection and migration techniques based on density of states estimation and k-means clustering, respectively. This work demonstrates the robustness and parallel performance of the SISLICE method on a representative set of SCF eigenvalue problems and outlines research directions that will be explored in future work.<\/jats:p>","DOI":"10.1145\/3409571","type":"journal-article","created":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T22:30:30Z","timestamp":1602887430000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A Shift Selection Strategy for Parallel Shift-invert Spectrum Slicing in Symmetric Self-consistent Eigenvalue Computation"],"prefix":"10.1145","volume":"46","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2735-3706","authenticated-orcid":false,"given":"David B.","family":"Williams-Young","sequence":"first","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA US"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Beckman","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Yang","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA US"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2014.03.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358194"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2005.07.004"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide (3rd ed.). Society for Industrial and Applied Mathematics Philadelphia PA. DOI:https:\/\/doi.org\/10.1137\/1.9780898719604  E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide (3rd ed.). Society for Industrial and Applied Mathematics Philadelphia PA. DOI:https:\/\/doi.org\/10.1137\/1.9780898719604","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii . 2007 . K-means++: The advantages of careful seeding . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 1027--1035. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283494. David Arthur and Sergei Vassilvitskii. 2007. K-means++: The advantages of careful seeding. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). Society for Industrial and Applied Mathematics, Philadelphia, PA, 1027--1035. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283494."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00104"},{"volume-title":"Proceedings of the 2nd Annual PGAS Applications Workshop. ACM, 7.","author":"Bachan John","key":"e_1_2_1_7_1","unstructured":"John Bachan , Dan Bonachea , Paul H. Hargrove , Steve Hofmeyr , Mathias Jacquelin , Amir Kamil , Brian van Straalen , and Scott B. Baden . 2017. The UPC++ PGAS library for exascale computing . In Proceedings of the 2nd Annual PGAS Applications Workshop. ACM, 7. John Bachan, Dan Bonachea, Paul H. Hargrove, Steve Hofmeyr, Mathias Jacquelin, Amir Kamil, Brian van Straalen, and Scott B. Baden. 2017. The UPC++ PGAS library for exascale computing. In Proceedings of the 2nd Annual PGAS Applications Workshop. ACM, 7."},{"key":"e_1_2_1_8_1","unstructured":"Zhaojun Bai James Demmel Jack Dongarra Axel Ruhe and Henk van der Vorst. 2000. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM.  Zhaojun Bai James Demmel Jack Dongarra Axel Ruhe and Henk van der Vorst. 2000. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4964861"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.jctc.7b01243"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"L. Blackford J. Choi A. Cleary E. D\u2019Azevedo J. Demmel I. Dhillon J. Dongarra S. Hammarling G. Henry A. Petitet K. Stanley D. Walker and R. Whaley. 1997. ScaLAPACK Users\u2019 Guide. Society for Industrial and Applied Mathematics. DOI:https:\/\/doi.org\/10.1137\/1.9780898719642  L. Blackford J. Choi A. Cleary E. D\u2019Azevedo J. Demmel I. Dhillon J. Dongarra S. Hammarling G. Henry A. Petitet K. Stanley D. Walker and R. Whaley. 1997. ScaLAPACK Users\u2019 Guide. Society for Industrial and Applied Mathematics. DOI:https:\/\/doi.org\/10.1137\/1.9780898719642","DOI":"10.1137\/1.9780898719642"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-012-9564-z"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479888151111"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(98)00192-1"},{"key":"e_1_2_1_16_1","unstructured":"George Karypis and Vipin Kumar. 2009. MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System Version 4.0. Retrieved from http:\/\/www.cs.umn.edu\/metis.  George Karypis and Vipin Kumar. 2009. MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System Version 4.0. Retrieved from http:\/\/www.cs.umn.edu\/metis."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.25350"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.24254"},{"volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916)","author":"Kestyn J.","key":"e_1_2_1_19_1","unstructured":"J. Kestyn , V. Kalantzis , E. Polizzi , and Y. Saad . 2016. PFEAST: A high performance sparse eigenvalue solver using distributed-memory linear solvers . In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916) . 178--189. J. Kestyn, V. Kalantzis, E. Polizzi, and Y. Saad. 2016. PFEAST: A high performance sparse eigenvalue solver using distributed-memory linear solvers. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916). 178--189."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500366124"},{"key":"e_1_2_1_21_1","unstructured":"Karol Kowalski Edoardo Apra Ray Bair Colleen Bertoni Jeffery S. Boschen Eric J. Bylaska Wibe A. de Jong Jr. Thom Dunning Niri Govind Robert J. Harrison Kris Keipert Sriram Krishnamoorthy Erdal Mutlu Ajay Panyala Ryan M. Richard T. P. Straatsma Edward F. Valeev Hubertus J. J. van Dam \u00c1lvaro V\u00e1zquez-Mayagoitia David B. Williams-Young Chao Yang and Theresa L. Windus. [n.d.]. NWChemEx\u2014Computational chemistry for the exascale era. Chem. Rev. ([n.d.]) in preparation.  Karol Kowalski Edoardo Apra Ray Bair Colleen Bertoni Jeffery S. Boschen Eric J. Bylaska Wibe A. de Jong Jr. Thom Dunning Niri Govind Robert J. Harrison Kris Keipert Sriram Krishnamoorthy Erdal Mutlu Ajay Panyala Ryan M. Richard T. P. Straatsma Edward F. Valeev Hubertus J. J. van Dam \u00c1lvaro V\u00e1zquez-Mayagoitia David B. Williams-Young Chao Yang and Theresa L. Windus. [n.d.]. NWChemEx\u2014Computational chemistry for the exascale era. Chem. Rev. ([n.d.]) in preparation."},{"volume-title":"Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods.","author":"Lehoucq Richard B.","key":"e_1_2_1_22_1","unstructured":"Richard B. Lehoucq , Danny C. Sorensen , and Chao Yang . 1998. ARPACK Users \u2019 Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. Vol. 6 . SIAM, Philadelphia , PA. Richard B. Lehoucq, Danny C. Sorensen, and Chao Yang. 1998. ARPACK Users\u2019 Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. Vol. 6. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1170935"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054493"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/130934283"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1088\/0953-8984\/26\/21\/213201"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.79.115112"},{"volume-title":"Numerical Methods for Large Eigenvalue Problems: Revised Edition","author":"Saad Yousef","key":"e_1_2_1_29_1","unstructured":"Yousef Saad . 2011. Numerical Methods for Large Eigenvalue Problems: Revised Edition . Vol. 66 . SIAM , Philadelphia, PA . Yousef Saad. 2011. Numerical Methods for Large Eigenvalue Problems: Revised Edition. Vol. 66. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(03)00565-X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00135-1"},{"key":"e_1_2_1_32_1","first-page":"158","article-title":"On fast factorization pivoting methods for sparse symmetric indefinite systems","volume":"23","author":"Schenk Olaf","year":"2006","unstructured":"Olaf Schenk and Klaus G\u00e4rtner . 2006 . On fast factorization pivoting methods for sparse symmetric indefinite systems . Electr. Trans. Numer. Anal. 23 , 1 (2006), 158 -- 179 . Olaf Schenk and Klaus G\u00e4rtner. 2006. On fast factorization pivoting methods for sparse symmetric indefinite systems. Electr. Trans. Numer. Anal. 23, 1 (2006), 158--179.","journal-title":"Electr. Trans. Numer. Anal."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022326604210"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01113273"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599363084"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1088\/0953-8984\/14\/11\/302"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/060661910"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786445208647087"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090866X"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1135542"},{"key":"e_1_2_1_41_1","series-title":"Series 16 (Jan","volume-title":"Solving large-scale eigenvalue problems in SciDAC applications. J. Phys.: Conf","author":"Yang Chao","year":"2005","unstructured":"Chao Yang . 2005. Solving large-scale eigenvalue problems in SciDAC applications. J. Phys.: Conf . Series 16 (Jan . 2005 ), 425--434. DOI:https:\/\/doi.org\/10.1088\/1742-6596\/16\/1\/058 Chao Yang. 2005. Solving large-scale eigenvalue problems in SciDAC applications. J. Phys.: Conf. Series 16 (Jan. 2005), 425--434. DOI:https:\/\/doi.org\/10.1088\/1742-6596\/16\/1\/058"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236464"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409571","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409571","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3409571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:41Z","timestamp":1750199921000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3409571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,16]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3409571"],"URL":"https:\/\/doi.org\/10.1145\/3409571","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2020,10,16]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}