{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:45:34Z","timestamp":1783035934082,"version":"3.54.6"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T00:00:00Z","timestamp":1726272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972033"],"award-info":[{"award-number":["61972033"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>AMG is one of the most efficient and widely used methods for solving sparse linear systems. The computational process of AMG mainly consists of a series of iterative calculations of generalized sparse matrix-matrix multiplication (SpGEMM) and sparse matrix-vector multiplication (SpMV). Optimizing these sparse matrix calculations is crucial for accelerating solving linear systems. In this paper, we first focus on optimizing the SpGEMM algorithm in AmgX, a popular AMG library for GPUs. We propose a new algorithm called SpGEMM-upper, which achieves an average speedup of 2.02\u00d7 on Tesla V100 and 1.96\u00d7 on RTX 3090 against the original algorithm. Next, through experimental investigation, we conclude that no single SpGEMM library or algorithm performs optimally for most sparse matrices, and the same holds true for SpMV. Therefore, we build machine learning-based models to predict the optimal SpGEMM and SpMV used in the AMG calculation process. Finally, we integrate the prediction models, SpGEMM-upper, and other selected algorithms into a framework for adaptive sparse matrix computation in AMG. Our experimental results prove that the framework achieves promising performance improvements on the test set.<\/jats:p>","DOI":"10.1145\/3664924","type":"journal-article","created":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T11:13:23Z","timestamp":1715771603000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimization of Sparse Matrix Computation for Algebraic Multigrid on GPUs"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1288-331X","authenticated-orcid":false,"given":"Yizhuo","family":"Wang","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1351-724X","authenticated-orcid":false,"given":"Fangli","family":"Chang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5420-8809","authenticated-orcid":false,"given":"Bingxin","family":"Wei","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3828-0015","authenticated-orcid":false,"given":"Jianhua","family":"Gao","sequence":"additional","affiliation":[{"name":"Beijing Normal University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3250-0435","authenticated-orcid":false,"given":"Weixing","family":"Ji","sequence":"additional","affiliation":[{"name":"Beijing Normal University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,14]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Algebraic Multigrid (AMG) for Automatic Multigrid Solution with Application to Geodetic Computations","author":"Brandt Achi","year":"1983","unstructured":"Achi Brandt, Steve McCormick, and John Ruge. Algebraic Multigrid (AMG) for Automatic Multigrid Solution with Application to Geodetic Computations. Technical report, Colorado State University, Fort Collins, CO. (1983)."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-018-0783-x"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751244"},{"key":"e_1_3_2_5_2","first-page":"496","article-title":"Sparse matrix format selection with multiclass SVM for SpMV on GPU","author":"Benatia Akrem","year":"2016","unstructured":"Akrem Benatia, Weixing Ji, Yizhuo Wang, and Feng Shi. 2016. Sparse matrix format selection with multiclass SVM for SpMV on GPU. In 45th International Conference on Parallel Processing (ICPP), 2016. 496\u2013505.","journal-title":"45th International Conference on Parallel Processing (ICPP)"},{"key":"e_1_3_2_6_2","first-page":"94","article-title":"Bridging the gap between deep learning and sparse matrix format selection","author":"Zhao Yue","year":"2018","unstructured":"Yue Zhao, Jiajia Li, Chunhua Liao, and Xipeng Shen. 2018. Bridging the gap between deep learning and sparse matrix format selection. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2018. 94\u2013108.","journal-title":"Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3330345.3330354"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.21105\/joss.01244"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/140980260"},{"key":"e_1_3_2_10_2","first-page":"30","volume-title":"Advances in Neural Information Processing Systems","year":"2017","unstructured":"Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. LightGBM: A highly efficient gradient boosting decision tree. Advances in Neural Information Processing Systems (2017), 30."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/wics.13"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1163\/156939387X00036"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/14063.14074"},{"key":"e_1_3_2_14_2","article-title":"Multi-grid methods and applications","author":"Hackbusch Wolfgang","year":"2013","unstructured":"Wolfgang Hackbusch. 2013. Multi-grid methods and applications. Springer Science & Business Media (2013)","journal-title":"Springer Science & Business Media"},{"key":"e_1_3_2_15_2","first-page":"73","article-title":"Algebraic multigrid","author":"Ruge John W.","year":"1987","unstructured":"John W. Ruge and Klaus St\u00fcben. 1987. Algebraic multigrid. Society for Industrial and Applied Mathematics (1987), 73\u2013130.","journal-title":"Society for Industrial and Applied Mathematics"},{"issue":"37","key":"e_1_3_2_16_2","first-page":"123","article-title":"An aggregation-based algebraic multigrid method","volume":"37","author":"Notay Yvan","year":"2010","unstructured":"Yvan Notay. 2010. An aggregation-based algebraic multigrid method. Electronic Transactions on Numerical Analysis 37, 37 (2010), 123\u2013146.","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/040614402"},{"issue":"2","key":"e_1_3_2_18_2","first-page":"133","article-title":"An energy-based AMG coarsening strategy","volume":"13","year":"2006","unstructured":"James Brannick, Marian Brezina, S. MacLachlan, T. Manteuffel, S. McCormick, and J. Ruge. 2006. An energy-based AMG coarsening strategy. Numerical Linear Algebra with Applications 13, 2--3 (2006), 133\u2013148.","journal-title":"Numerical Linear Algebra with Applications"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"e_1_3_2_20_2","unstructured":"Kokkos Kernels. [Online]. Available: https:\/\/github.com\/kokkos\/kokkos-kernels"},{"key":"e_1_3_2_21_2","unstructured":"NVIDIA. Nvidia cuSPARSE Library. [Online]. Available: https:\/\/developer.nvidia.com\/cusparse"},{"key":"e_1_3_2_22_2","unstructured":"Intel. Intel Math Kernel Library. [Online]. Available: https:\/\/software.intel.com\/en-us\/mkl"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/130948811"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_3_2_25_2","article-title":"Better size estimation for sparse matrix products","volume":"69","author":"Resen Amossen Rasmus","year":"2014","unstructured":"Rasmus Resen Amossen, Andrea Campagna, and Rasmus Pagh. 2014. Better size estimation for sparse matrix products. Algorithmica 69 (2014), 741\u201357.","journal-title":"Algorithmica"},{"key":"e_1_3_2_26_2","first-page":"750","article-title":"The input\/output complexity of sparse matrix multiplication","author":"Pagh Rasmus","year":"2014","unstructured":"Rasmus Pagh and Morten St\u00f6ckel. 2014. The input\/output complexity of sparse matrix multiplication. In European Symposium on Algorithms (2014), 750\u2013761.","journal-title":"European Symposium on Algorithms"},{"key":"e_1_3_2_27_2","unstructured":"Steven Dalton Nathan Bell Luke Olson and Michael Garland. 2014. CUSP: Generic Parallel Algorithms for Sparse Matrix and Graph Computations. 2014. http:\/\/cusplibrary.github.io\/Version0.5.0."},{"key":"e_1_3_2_28_2","first-page":"1","article-title":"On the representation and multiplication of hypersparse matrices","author":"Buluc Aydin","year":"2008","unstructured":"Aydin Buluc and John R. Gilbert. 2008. On the representation and multiplication of hypersparse matrices. In IEEE International Symposium on Parallel and Distributed Processing (2008), 1\u201311.","journal-title":"IEEE International Symposium on Parallel and Distributed Processing"},{"key":"e_1_3_2_29_2","first-page":"370","article-title":"An efficient GPU general sparse matrix-matrix multiplication for irregular data","author":"Liu Weifeng","year":"2014","unstructured":"Weifeng Liu and Brian Vinter. 2014. An efficient GPU general sparse matrix-matrix multiplication for irregular data. In IEEE 28th International Parallel and Distributed Processing Symposium (2014), 370\u2013381.","journal-title":"IEEE 28th International Parallel and Distributed Processing Symposium"},{"key":"e_1_3_2_30_2","first-page":"101","article-title":"High-performance and memory-saving sparse general matrix-matrix multiplication for NVIDIA Pascal GPU","author":"Nagasaka Yusuke","year":"2017","unstructured":"Yusuke Nagasaka, Akira Nukada, and Satoshi Matsuoka. 2017. High-performance and memory-saving sparse general matrix-matrix multiplication for NVIDIA Pascal GPU. In 46th International Conference on Parallel Processing (ICPP) (2017), 101\u2013110.","journal-title":"46th International Conference on Parallel Processing (ICPP)"},{"key":"e_1_3_2_31_2","first-page":"68","article-title":"Adaptive sparse matrix-matrix multiplication on the GPU","year":"2019","unstructured":"Martin Winter, Daniel Mlakar, Rhaleb Zayer, Hans-Peter Seidel, and Markus Steinberger. 2019. Adaptive sparse matrix-matrix multiplication on the GPU. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (PPoPP) (2019), 68\u201381.","journal-title":"Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (PPoPP)"},{"key":"e_1_3_2_32_2","first-page":"283","article-title":"Characterization of data movement requirements for sparse matrix computations on GPUs","year":"2017","unstructured":"Sireyya Emre Kurt, Vineeth Thumma, Changwan Hong, Aravind Sukumaran-Rajam, and P. Sadayappan. 2017. Characterization of data movement requirements for sparse matrix computations on GPUs. In IEEE 24th International Conference on High Performance Computing (HiPC). 283\u2013293.","journal-title":"IEEE 24th International Conference on High Performance Computing (HiPC)"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732227"},{"key":"e_1_3_2_34_2","unstructured":"Sashikumaar Ganesan and Manan Shah. 2020. SParSH-AMG: A library for hybrid CPU-GPU algebraic multigrid and preconditioned iterative methods. arXiv preprint arXiv:2007.00056 2020."},{"key":"e_1_3_2_35_2","first-page":"632","article-title":"HYPRE: A library of high performance preconditioners","author":"Falgout Robert D.","year":"2002","unstructured":"Robert D. Falgout and Ulrike Meier Yang. 2002. HYPRE: A library of high performance preconditioners. In International Conference on Computational Science (2002), 632\u2013641.","journal-title":"International Conference on Computational Science"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1145\/3332466.3374521","article-title":"spECK: Accelerating GPU sparse matrix-matrix multiplication through lightweight analysis","author":"Parger Mathias","year":"2020","unstructured":"Mathias Parger, Martin Winter, Daniel Mlakar, and Markus Steinberger. 2020. spECK: Accelerating GPU sparse matrix-matrix multiplication through lightweight analysis. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2020), 362\u2013375.","journal-title":"Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3196940"},{"key":"e_1_3_2_38_2","first-page":"1","article-title":"Implementing sparse matrix-vector multiplication on throughput-oriented processors","author":"Bell Nathan","year":"2009","unstructured":"Nathan Bell and Michael Garland. 2009. Implementing sparse matrix-vector multiplication on throughput-oriented processors. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (2009), 1\u201311.","journal-title":"Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/SC.2014.68","article-title":"Efficient sparse matrix-vector multiplication on GPUs using the CSR storage format","author":"Greathouse Joseph L.","year":"2014","unstructured":"Joseph L. Greathouse and Mayank Daga. 2014. Efficient sparse matrix-vector multiplication on GPUs using the CSR storage format. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis 2014, 769\u2013780.","journal-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis"},{"key":"e_1_3_2_40_2","first-page":"64","article-title":"Structural agnostic SpMV: Adapting CSR-adaptive for irregular matrices","author":"Daga Mayank","year":"2015","unstructured":"Mayank Daga and Joseph L. Greathouse. 2015. Structural agnostic SpMV: Adapting CSR-adaptive for irregular matrices. In IEEE 22nd International Conference on High Performance Computing (HiPC) 2015, 64\u201374.","journal-title":"IEEE 22nd International Conference on High Performance Computing (HiPC)"},{"issue":"1","key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1109\/JSEN.2021.3128130","article-title":"An open-source tool for classification models in resource-constrained hardware","volume":"22","author":"Tsutsui da Silva Lucas","year":"2021","unstructured":"Lucas Tsutsui da Silva, Vinicius M. A. de Souza, and Gustavo EAPA Batista. 2021. An open-source tool for classification models in resource-constrained hardware. IEEE Sensors Journal 22, 1 (2021), 544\u2013554.","journal-title":"IEEE Sensors Journal"},{"issue":"1","key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0168-9274(01)00115-5","article-title":"BoomerAMG: A parallel algebraic multigrid solver and preconditioner","volume":"41","author":"Meier Yang Ulrike","year":"2002","unstructured":"Ulrike Meier Yang. 2002. BoomerAMG: A parallel algebraic multigrid solver and preconditioner. Applied Numerical Mathematics 41, 1 (2002), 155\u2013177.","journal-title":"Applied Numerical Mathematics"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190647"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/110838844"},{"key":"e_1_3_2_45_2","first-page":"1","article-title":"High-performance algebraic multigrid solver optimized for multi-core based distributed parallel systems","year":"2015","unstructured":"Jongsoo Park, Mikhail Smelyanskiy, Ulrike Meier Yang, Dheevatsa Mudigere, and Pradeep Dubey. 2015. High-performance algebraic multigrid solver optimized for multi-core based distributed parallel systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 1\u201312.","journal-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-018-0604-8"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M104253X"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2019.102545"},{"key":"e_1_3_2_49_2","first-page":"293","article-title":"Bandwidth optimized parallel algorithms for sparse matrix-matrix multiplication using propagation blocking","author":"Gu Zhixiang","year":"2020","unstructured":"Zhixiang Gu, Jose Moreira, David Edelsohn, and Ariful Azad. 2020. Bandwidth optimized parallel algorithms for sparse matrix-matrix multiplication using propagation blocking. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020. 293\u2013303.","journal-title":"Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures"},{"key":"e_1_3_2_50_2","first-page":"90","article-title":"TileSpGEMM: A tiled algorithm for parallel sparse general matrix-matrix multiplication on GPUs","year":"2022","unstructured":"Yuyao Niu, Zhengyang Lu, Haonan Ji, Shuhui Song, Zhou Jin, and Weifeng Liu. 2022. TileSpGEMM: A tiled algorithm for parallel sparse general matrix-matrix multiplication on GPUs. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2022. 90\u2013106.","journal-title":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming"},{"issue":"12","key":"e_1_3_2_51_2","first-page":"1","article-title":"A systematic survey of general sparse matrix-matrix multiplication","volume":"55","year":"2023","unstructured":"Jianhua Gao, Weixing Ji, Fangli Chang, Shiyu Han, Bingxin Wei, Zeming Liu, and Yizhuo Wang. 2023. A systematic survey of general sparse matrix-matrix multiplication. ACM Computing Surveys 55, 12 (2023), 1\u201336.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1026419"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664924","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3664924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:47Z","timestamp":1750291427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,14]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3664924"],"URL":"https:\/\/doi.org\/10.1145\/3664924","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,14]]},"assertion":[{"value":"2023-09-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}