{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T15:28:55Z","timestamp":1759937335498,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T00:00:00Z","timestamp":1695340800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>We address the communication overhead of distributed sparse matrix-(multiple)-vector multiplication in the context of large-scale eigensolvers, using filter diagonalization as an example. The basis of our study is a performance model, which includes a communication metric that is computed directly from the matrix sparsity pattern without running any code. The performance model quantifies to which extent scalability and parallel efficiency are lost due to communication overhead.<\/jats:p>\n          <jats:p>To restore scalability, we identify two orthogonal layers of parallelism in the filter diagonalization technique. In the horizontal layer the rows of the sparse matrix are distributed across individual processes. In the vertical layer bundles of multiple vectors are distributed across separate process groups. An analysis in terms of the communication metric predicts that scalability can be restored if, and only if, one implements the two orthogonal layers of parallelism via different distributed vector layouts.<\/jats:p>\n          <jats:p>Our theoretical analysis is corroborated by benchmarks for application matrices from quantum and solid state physics, road networks, and nonlinear programming. We finally demonstrate the benefits of using orthogonal layers of parallelism with two exemplary application cases\u2014an exciton and a strongly correlated electron system\u2014which incur either small or large communication overhead.<\/jats:p>","DOI":"10.1145\/3614444","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T12:03:12Z","timestamp":1691496192000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Orthogonal Layers of Parallelism in Large-Scale Eigenvalue Computations"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0367-2721","authenticated-orcid":false,"given":"Andreas","family":"Alvermann","sequence":"first","affiliation":[{"name":"Universit\u00e4t Greifswald, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8723-2781","authenticated-orcid":false,"given":"Georg","family":"Hager","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2146-8203","authenticated-orcid":false,"given":"Holger","family":"Fehske","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Greifswald, Germany and Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,9,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_3_2_2","DOI":"10.1016\/j.parco.2016.10.001"},{"doi-asserted-by":"publisher","key":"e_1_3_3_3_2","DOI":"10.1109\/TPDS.2022.3223512"},{"unstructured":"Andreas Alvermann. 2022. ScaMaC\u2014A Scalable Matrix Collection. Retrieved from www.bitbucket.org\/essex\/matrixcollection","key":"e_1_3_3_4_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_5_2","DOI":"10.1088\/1361-6455\/aaa060"},{"doi-asserted-by":"publisher","key":"e_1_3_3_6_2","DOI":"10.1103\/PhysRevB.84.035126"},{"doi-asserted-by":"publisher","key":"e_1_3_3_7_2","DOI":"10.1007\/978-3-642-21831-6"},{"doi-asserted-by":"publisher","key":"e_1_3_3_8_2","DOI":"10.1145\/1527286.1527287"},{"key":"e_1_3_3_9_2","volume-title":"Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods","author":"Barrett R.","year":"1993","unstructured":"R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. Van der Vorst. 1993. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, PA."},{"doi-asserted-by":"publisher","key":"e_1_3_3_10_2","DOI":"10.1137\/1.9780898719642"},{"key":"e_1_3_3_11_2","article-title":"ILUPACK\u2014Preconditioning Software Package","author":"Bollh\u00f6fer M.","year":"2016","unstructured":"M. Bollh\u00f6fer, Y. Saad, and O. Schenk. 2016. ILUPACK\u2014Preconditioning Software Package. Retrieved from www.icm.tu-bs.de\/bolle\/ilupack\/","journal-title":"R"},{"doi-asserted-by":"publisher","key":"e_1_3_3_12_2","DOI":"10.3233\/SPR-2012-0342"},{"key":"e_1_3_3_13_2","volume-title":"Lanczos Algorithms for Large Symmetric Eigenvalue Computations","author":"Cullum Jane K.","year":"1985","unstructured":"Jane K. Cullum and Ralph A. Willoughby. 1985. Lanczos Algorithms for Large Symmetric Eigenvalue Computations. Vols. I & II. Birkh\u00e4user, Boston."},{"doi-asserted-by":"publisher","key":"e_1_3_3_14_2","DOI":"10.1103\/RevModPhys.66.763"},{"doi-asserted-by":"publisher","key":"e_1_3_3_15_2","DOI":"10.1145\/2049662.2049663"},{"doi-asserted-by":"publisher","key":"e_1_3_3_16_2","DOI":"10.1103\/RevModPhys.93.041002"},{"doi-asserted-by":"publisher","key":"e_1_3_3_17_2","DOI":"10.1137\/080731992"},{"unstructured":"T. A. Davis et al.2023. SuiteSparse : A Suite of Sparse Matrix Software. Retrieved from https:\/\/github.com\/DrTimothyAldenDavis\/SuiteSparse","key":"e_1_3_3_18_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_19_2","DOI":"10.1137\/S1064827596300073"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-319-62426-6_5","volume-title":"Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing","author":"Galgon Martin","year":"2017","unstructured":"Martin Galgon, Lukas Kr\u00e4mer, Bruno Lang, Andreas Alvermann, Holger Fehske, Andreas Pieper, Georg Hager, Moritz Kreutzer, Faisal Shahzad, Gerhard Wellein, Achim Basermann, Melven R\u00f6hrig-Z\u00f6llner, and Jonas Thies. 2017. Improved coefficients for polynomial filtering in ESSEX. In Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing, Tetsuya Sakurai, Shao-Liang Zhang, Toshiyuki Imamura, Yusaku Yamamoto, Yoshinobu Kuramashi, and Takeo Hoshi (Eds.). Springer International Publishing, Cham, 63\u201379."},{"doi-asserted-by":"publisher","key":"e_1_3_3_21_2","DOI":"10.5555\/1855048"},{"doi-asserted-by":"publisher","key":"e_1_3_3_22_2","DOI":"10.1145\/1089014.1089019"},{"doi-asserted-by":"publisher","key":"e_1_3_3_23_2","DOI":"10.1002\/nla.2447"},{"doi-asserted-by":"publisher","key":"e_1_3_3_24_2","DOI":"10.1007\/978-0-387-09766-4_500"},{"doi-asserted-by":"publisher","key":"e_1_3_3_25_2","DOI":"10.1038\/nature13832"},{"doi-asserted-by":"publisher","key":"e_1_3_3_26_2","DOI":"10.1007\/978-3-540-38347-5"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-319-92040-5_17","volume-title":"High Performance Computing","author":"Kreutzer Moritz","year":"2018","unstructured":"Moritz Kreutzer, Dominik Ernst, Alan R. Bishop, Holger Fehske, Georg Hager, Kengo Nakajima, and Gerhard Wellein. 2018. Chebyshev filter diagonalization on modern manycore processors and GPGPUs. In High Performance Computing, Rio Yokota, Mich\u00e8le Weiland, David Keyes, and Carsten Trinitis (Eds.). Springer International Publishing, Cham, 329\u2013349."},{"doi-asserted-by":"publisher","key":"e_1_3_3_28_2","DOI":"10.1137\/130930352"},{"doi-asserted-by":"publisher","key":"e_1_3_3_29_2","DOI":"10.1007\/s10766-016-0464-z"},{"doi-asserted-by":"publisher","key":"e_1_3_3_30_2","DOI":"10.1007\/BF01385896"},{"key":"e_1_3_3_31_2","article-title":"ARPACK Users\u2019 Guide","author":"Lehoucq R. B.","year":"1998","unstructured":"R. B. Lehoucq, D. C. Sorensen, and C. Yang. 1998. ARPACK Users\u2019 Guide. Retrieved from http:\/\/www.caam.rice.edu\/software\/ARPACK\/","journal-title":"R"},{"doi-asserted-by":"publisher","key":"e_1_3_3_32_2","DOI":"10.1137\/18M1170935"},{"doi-asserted-by":"publisher","key":"e_1_3_3_33_2","DOI":"10.21468\/SciPostPhys.11.2.021"},{"unstructured":"John D. McCalpin. 1995. Memory bandwidth and machine balance in current high performance computers. IEEE Comput. Soc. Technic. Commit. Comput. Archit. Newslett. Dec. (1995).","key":"e_1_3_3_34_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_35_2","DOI":"10.1145\/1654059.1654096"},{"doi-asserted-by":"publisher","key":"e_1_3_3_36_2","DOI":"10.1177\/1094342020959423"},{"doi-asserted-by":"publisher","key":"e_1_3_3_37_2","DOI":"10.1016\/j.jcp.2016.08.027"},{"doi-asserted-by":"publisher","key":"e_1_3_3_38_2","DOI":"10.21468\/SciPostPhys.5.5.045"},{"doi-asserted-by":"publisher","key":"e_1_3_3_39_2","DOI":"10.1103\/PhysRevB.79.115112"},{"unstructured":"PARDISO Solver Project. 2022. Retrieved from http:\/\/www.pardiso-project.org\/","key":"e_1_3_3_40_2"},{"doi-asserted-by":"publisher","key":"e_1_3_3_41_2","DOI":"10.1137\/140976017"},{"doi-asserted-by":"publisher","key":"e_1_3_3_42_2","DOI":"10.1137\/060648945"},{"doi-asserted-by":"publisher","key":"e_1_3_3_43_2","DOI":"10.1137\/1.9781611970739"},{"doi-asserted-by":"publisher","key":"e_1_3_3_44_2","DOI":"10.1137\/070707002"},{"doi-asserted-by":"publisher","key":"e_1_3_3_45_2","DOI":"10.1038\/s41467-021-24726-0"},{"doi-asserted-by":"publisher","key":"e_1_3_3_46_2","DOI":"10.1126\/science.aaa7432"},{"doi-asserted-by":"publisher","key":"e_1_3_3_47_2","DOI":"10.1103\/PhysRevLett.125.156601"},{"doi-asserted-by":"publisher","key":"e_1_3_3_48_2","DOI":"10.1137\/S0895479894270427"},{"doi-asserted-by":"publisher","key":"e_1_3_3_49_2","DOI":"10.1017\/S0962492902000089"},{"doi-asserted-by":"publisher","key":"e_1_3_3_50_2","DOI":"10.1137\/S1064827500370883"},{"doi-asserted-by":"publisher","key":"e_1_3_3_51_2","DOI":"10.1103\/RevModPhys.78.275"},{"doi-asserted-by":"publisher","key":"e_1_3_3_52_2","DOI":"10.1145\/3313828"},{"doi-asserted-by":"publisher","key":"e_1_3_3_53_2","DOI":"10.1109\/IPDPS.2019.00057"},{"key":"e_1_3_3_54_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-319-17353-5_2","volume-title":"High Performance Computing for Computational Science \u2013 VECPAR 2014","author":"Yamazaki Ichitaro","year":"2015","unstructured":"Ichitaro Yamazaki, Stanimire Tomov, Tingxing Dong, and Jack Dongarra. 2015. Mixed-precision orthogonalization scheme and adaptive step size for improving the stability and performance of CA-GMRES on GPUs. In High Performance Computing for Computational Science \u2013 VECPAR 2014, Michel Dayd\u00e9, Osni Marques, and Kengo Nakajima (Eds.). Springer International Publishing, Cham, 17\u201330."},{"doi-asserted-by":"publisher","key":"e_1_3_3_55_2","DOI":"10.1016\/j.jcp.2006.03.017"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3614444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3614444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:30Z","timestamp":1750287030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3614444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,22]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3614444"],"URL":"https:\/\/doi.org\/10.1145\/3614444","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2023,9,22]]},"assertion":[{"value":"2022-09-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}