{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T20:06:40Z","timestamp":1778962000862,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T00:00:00Z","timestamp":1778889600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T00:00:00Z","timestamp":1778889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2026,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We present an optimised distributed-memory algorithm for the unpreconditioned conjugate gradient (CG) method. We experiment with using the CG algorithm with the compressed sparse row (CSR), compressed sparse row\u00a05 (CSR5), compressed sparse row\u00a02 (CSR2) and symmetric compressed sparse row (SCSR) sparse matrix formats. For the CG algorithm, we present a CSR5-based and an SCSR-based distributed-memory sparse matrix-vector multiplication (SpMV) algorithm. We developed five distributed-memory CG implementations using different combinations of the mentioned sparse matrix formats and SpMV algorithms. We benchmarked our implementations on a distributed-memory computer cluster with Intel x86-64 CPUs. For the maximum benchmarked number of compute nodes, the median performance of our optimised distributed-memory CG algorithm with CSR-based SpMV was 58\u00a0%\u00a0greater than of the state-of-the-art PETSc library, and the median performance of our optimised distributed-memory CG algorithm with SCSR-based SpMV was 105\u00a0%\u00a0greater than of the PETSc library.<\/jats:p>","DOI":"10.1007\/s10766-026-00821-x","type":"journal-article","created":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T19:11:28Z","timestamp":1778958688000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accelerating the Conjugate Gradient Method on Distributed-Memory Computers"],"prefix":"10.1007","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6663-969X","authenticated-orcid":false,"given":"Claudio","family":"Kozick\u00fd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8948-8721","authenticated-orcid":false,"given":"Ivan","family":"\u0160ime\u010dek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"R\u00fara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,16]]},"reference":[{"key":"821_CR1","unstructured":"Wilkinson, J.H.: Introduction to Part\u00a0II: The Algebraic Eigenvalue Problem. Handbook for Automatic Computation, vol. 2, pp. 191\u2013201. Springer, Berlin, Heidelberg (1971)"},{"key":"821_CR2","volume-title":"An Introduction to Numerical Analysis","author":"KE Atkinson","year":"1989","unstructured":"Atkinson, K.E.: An Introduction to Numerical Analysis, 2nd edn. John Wiley & Sons, United States (1989)","edition":"2"},{"issue":"2","key":"821_CR3","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1145\/567806.567810","volume":"28","author":"IS Duff","year":"2002","unstructured":"Duff, I.S., Heroux, M.A., Pozo, R.: An overview of the Sparse Basic Linear Algebra Subprograms: The new standard from the BLAS Technical Forum. ACM Trans. Math. Softw. 28(2), 239\u2013267 (2002). https:\/\/doi.org\/10.1145\/567806.567810","journal-title":"ACM Trans. Math. Softw."},{"issue":"6","key":"821_CR4","doi-asserted-by":"publisher","first-page":"409","DOI":"10.6028\/jres.049.044","volume":"49","author":"MR Hestenes","year":"1952","unstructured":"Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49(6), 409\u2013436 (1952). https:\/\/doi.org\/10.6028\/jres.049.044","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"821_CR5","doi-asserted-by":"publisher","unstructured":"Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia (2003). https:\/\/doi.org\/10.1137\/1.9780898718003","DOI":"10.1137\/1.9780898718003"},{"key":"821_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.rico.2023.100213","volume":"10","author":"H Ping","year":"2023","unstructured":"Ping, H., Wang, Y., Wei, C., Xi, J., Zhang, T., Gao, Y.: DCG: An efficient distributed conjugate gradient algorithm for solving linear equations in multi-agent networks. Res. Control Optimization 10, 1\u201315 (2023). https:\/\/doi.org\/10.1016\/j.rico.2023.100213","journal-title":"Res. Control Optimization"},{"key":"821_CR7","doi-asserted-by":"publisher","unstructured":"Dongarra, J., Heroux, M.A.: Toward a new metric for ranking high performance computing systems. Technical Report SAND2013-4744, Sandia National Laboratories, Albuquerque, NM (2013). https:\/\/doi.org\/10.2172\/1089988","DOI":"10.2172\/1089988"},{"key":"821_CR8","doi-asserted-by":"publisher","unstructured":"Balay, S., Abhyankar, S., Adams, M., Brown, J., Brune, P.R., Buschelman, K., Dalcin, L., Dener, A., Eijkhout, V., Gropp, W.D., Karpeyev, D., Kaushik, D., Knepley, M.G., May, D.A., McInnes, L.C., Mills, R.T., Munson, T., Rupp, K., Sanan, P., Smith, B.F., Zampini, S., Zhang, H.: PETSc users manual: Revision\u00a03.15. Technical Report ANL-95\/11 Rev\u00a03.15, Argonne National Laboratory, Argonne, IL (2021). https:\/\/doi.org\/10.2172\/1814627","DOI":"10.2172\/1814627"},{"key":"821_CR9","doi-asserted-by":"publisher","unstructured":"Liu, W., Vinter, B.: CSR5: An efficient storage format for cross-platform sparse matrix-vector multiplication. In: Proceedings of the 29th ACM International Conference on Supercomputing, pp. 339\u2013350. Association for Computing Machinery, New York, NY, United States (2015). https:\/\/doi.org\/10.1145\/2751205.2751209","DOI":"10.1145\/2751205.2751209"},{"key":"821_CR10","doi-asserted-by":"publisher","unstructured":"Bian, H., Huang, J., Dong, R., Liu, L., Wang, X.: CSR2: A new format for SIMD-accelerated SpMV. In: Proceedings of the 20th IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing, pp. 350\u2013359. IEEE, United States (2020). https:\/\/doi.org\/10.1109\/CCGrid49817.2020.00-58","DOI":"10.1109\/CCGrid49817.2020.00-58"},{"issue":"1","key":"821_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2049662.2049663","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1\u20131125 (2011). https:\/\/doi.org\/10.1145\/2049662.2049663","journal-title":"ACM Trans. Math. Softw."},{"issue":"3","key":"821_CR12","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.parco.2008.12.006","volume":"35","author":"S Williams","year":"2009","unstructured":"Williams, S., Oliker, L., Vuduc, R., Shalf, J., Yelick, K., Demmel, J.: Optimization of sparse matrix-vector multiplication on emerging multicore platforms. Parallel Comput. 35(3), 178\u2013194 (2009). https:\/\/doi.org\/10.1016\/j.parco.2008.12.006","journal-title":"Parallel Comput."},{"key":"821_CR13","doi-asserted-by":"publisher","unstructured":"Yamazaki, I., Hoemmen, M., Luszczek, P., Dongarra, J.: Improving performance of GMRES by reducing communication and pipelining global collectives. In: Proceedings of the 31st IEEE International Parallel and Distributed Processing Symposium Workshops, pp. 1118\u20131127. IEEE, United States (2017). https:\/\/doi.org\/10.1109\/IPDPSW.2017.65","DOI":"10.1109\/IPDPSW.2017.65"},{"issue":"1","key":"821_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/12086563X","volume":"35","author":"P Ghysels","year":"2013","unstructured":"Ghysels, P., Ashby, T.J., Meerbergen, K., Vanroose, W.: Hiding global communication latency in the GMRES algorithm on massively parallel machines. SIAM J. Sci. Comput. 35(1), 48\u201371 (2013). https:\/\/doi.org\/10.1137\/12086563X","journal-title":"SIAM J. Sci. Comput."},{"issue":"11","key":"821_CR15","doi-asserted-by":"publisher","first-page":"2507","DOI":"10.1109\/TPDS.2019.2917663","volume":"30","author":"S Cools","year":"2019","unstructured":"Cools, S., Cornelis, J., Vanroose, W.: Numerically stable recurrence relations for the communication hiding pipelined conjugate gradient method. IEEE Trans. Parallel Distrib. Syst. 30(11), 2507\u20132522 (2019). https:\/\/doi.org\/10.1109\/TPDS.2019.2917663","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"5","key":"821_CR16","doi-asserted-by":"publisher","first-page":"3549","DOI":"10.1137\/16M1103361","volume":"40","author":"EC Carson","year":"2018","unstructured":"Carson, E.C., Rozlo\u017en\u00edk, M., Strako\u0161, Z., Tich\u00fd, P., T\u016fma, M.: The numerical stability analysis of pipelined conjugate gradient methods: Historical context and methodology. SIAM J. Sci. Comput. 40(5), 3549\u20133580 (2018). https:\/\/doi.org\/10.1137\/16M1103361","journal-title":"SIAM J. Sci. Comput."},{"key":"821_CR17","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.14209960","author":"C Kozick\u00fd","year":"2024","unstructured":"Kozick\u00fd, C., \u0160ime\u010dek, I., R\u00fara, B.: Accelerating the Conjugate Gradient Method on Distributed-Memory Computers: Software and Experiment Data. Zenodo (2024). https:\/\/doi.org\/10.5281\/zenodo.14209960","journal-title":"Zenodo"},{"issue":"4","key":"821_CR18","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1109\/TPDS.2021.3084070","volume":"33","author":"J Zhang","year":"2022","unstructured":"Zhang, J., Brown, J., Balay, S., Faibussowitsch, J., Knepley, M., Marin, O., Mills, R.T., Munson, T., Smith, B.F., Zampini, S.: The PetscSF scalable communication layer. IEEE Trans. Parallel Distrib. Syst. 33(4), 842\u2013853 (2022). https:\/\/doi.org\/10.1109\/TPDS.2021.3084070","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-026-00821-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-026-00821-x","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-026-00821-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T19:11:30Z","timestamp":1778958690000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-026-00821-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,16]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["821"],"URL":"https:\/\/doi.org\/10.1007\/s10766-026-00821-x","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,16]]},"assertion":[{"value":"25 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"11"}}