{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:38:53Z","timestamp":1760143133148,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:00:00Z","timestamp":1705017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Matrix\u2013matrix multiplication is of singular importance in linear algebra operations with a multitude of applications in scientific and engineering computing. Data structures for storing matrix elements are designed to minimize overhead information as well as to optimize the operation count. In this study, we utilize the notion of the compact diagonal storage method (CDM), which builds upon the previously developed diagonal storage\u2014an orientation-independent uniform scheme to store the nonzero elements of a range of matrices. This study exploits both these storage schemes and presents efficient GPU-accelerated parallel implementations of matrix multiplication when the input matrices are banded and\/or structured sparse. We exploit the data layouts in the diagonal storage schemes to expose a substantial amount of fine-grained parallelism and effectively utilize the GPU shared memory to improve the locality of data access for numerical calculations. Results from an extensive set of numerical experiments with the aforementioned types of matrices demonstrate orders-of-magnitude speedups compared with the sequential performance.<\/jats:p>","DOI":"10.3390\/a17010031","type":"journal-article","created":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T03:54:34Z","timestamp":1705031674000},"page":"31","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["GPU Algorithms for Structured Sparse Matrix Multiplication with Diagonal Storage Schemes"],"prefix":"10.3390","volume":"17","author":[{"given":"Sardar Anisul","family":"Haque","sequence":"first","affiliation":[{"name":"School of Computing and Data Science, Oryx Universal College in Partnership with Liverpool John Moores University (UK), Doha P.O. Box 12253, Qatar"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Tanvir","family":"Parvez","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, College of Computer, Qassim University, Buraydah 52571, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahadat","family":"Hossain","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Northern British Columbia, Prince George, BC V2N 4Z9, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,1,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Abdullah, W.M., Awosoga, D., and Hossain, S. (2022, January 19\u201323). Efficient Calculation of Triangle Centrality in Big Data Networks. Proceedings of the 2022 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC55821.2022.9926324"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3571157","article-title":"A systematic survey of general sparse matrix-matrix multiplication","volume":"55","author":"Gao","year":"2023","journal-title":"ACM Comput. Surv."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Kepner, J., and Gilbert, J. (2011). Graph Algorithms in the Language of Linear Algebra, SIAM.","DOI":"10.1137\/1.9780898719918"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Kepner, J., and Jananthan, H. (2018). Mathematics of Big Data: Spreadsheets, Databases, Matrices, and Graphs, MIT Press.","DOI":"10.7551\/mitpress\/10617.001.0001"},{"key":"ref_5","unstructured":"Shen, L., Dong, Y., Fang, B., Shi, J., Wang, X., Pan, S., and Shi, R. (2022, January 10\u201314). ABNN2: Secure two-party arbitrary-bitwidth quantized neural network predictions. Proceedings of the 59th ACM\/IEEE Design Automation Conference, San Francisco, CA, USA."},{"key":"ref_6","unstructured":"Gholami, A., Kim, S., Dong, Z., Yao, Z., Mahoney, M.W., and Keutzer, K. (2022). Low-Power Computer Vision, Chapman and Hall\/CRC."},{"key":"ref_7","unstructured":"Gundersen, G. (2002). The Use of Java Arrays in Matrix Computation. [Master\u2019s Thesis, University of Bergen]."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1177\/1094342013501126","article-title":"Optimization of quasi-diagonal matrix\u2013vector multiplication on GPU","volume":"28","author":"Yang","year":"2014","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Benner, P., Dufrechou, E., Ezzatti, P., Igounet, P., Quintana-Ort\u00ed, E.S., and Rem\u00f3n, A. (July, January 30). Accelerating band linear algebra operations on GPUs with application in model reduction. Proceedings of the Computational Science and Its Applications\u2013ICCSA 2014: 14th International Conference, Guimar\u00e3es, Portugal. Proceedings, Part VI 14.","DOI":"10.1007\/978-3-319-09153-2_29"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Dufrechou, E., Ezzatti, P., Quintana-Ort\u00ed, E.S., and Rem\u00f3n, A. (2014, January 20\u201322). Efficient symmetric band matrix-matrix multiplication on GPUs. Proceedings of the Latin American High Performance Computing Conference, Valparaiso, Chile.","DOI":"10.1007\/978-3-662-45483-1_1"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(76)90077-6","article-title":"Matrix multiplication by diagonals on a vector\/parallel processor","volume":"5","author":"Madsen","year":"1976","journal-title":"Inf. Process. Lett."},{"key":"ref_12","unstructured":"Tsao, A., and Turnbull, T. (1993). A Comparison of Algorithms for Banded Matrix Multiplication, Citeseer."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Vooturi, D.T., Kothapalli, K., and Bhalla, U.S. (2017, January 18\u201321). Parallelizing Hines matrix solver in neuron simulations on GPU. Proceedings of the 2017 IEEE 24th International Conference on High Performance Computing (HiPC), Jaipur, India.","DOI":"10.1109\/HiPC.2017.00051"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1351","DOI":"10.1007\/s10586-015-0489-x","article-title":"Unleashing GPU acceleration for symmetric band linear algebra kernels and model reduction","volume":"18","author":"Benner","year":"2015","journal-title":"Clust. Comput."},{"key":"ref_15","unstructured":"Kirk, D.B., and Wen-Mei, W.H. (2016). Programming Massively Parallel Processors: A Hands-On Approach, Morgan Kaufmann."},{"key":"ref_16","unstructured":"Munshi, A., Gaster, B., Mattson, T.G., and Ginsburg, D. (2011). OpenCL Programming Guide, Pearson Education."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Volkov, V., and Demmel, J.W. (2008, January 15\u201321). Benchmarking GPUs to tune dense linear algebra. Proceedings of the SC\u201908: Proceedings of the 2008 ACM\/IEEE conference on Supercomputing, Austin, TX, USA.","DOI":"10.1109\/SC.2008.5214359"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2045","DOI":"10.1109\/TPDS.2011.311","article-title":"Autotuning GEMM kernels for the Fermi GPU","volume":"23","author":"Kurzak","year":"2012","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1093\/comjnl\/bxt038","article-title":"Fastspmm: An efficient library for sparse matrix matrix product on gpus","volume":"57","author":"Ortega","year":"2014","journal-title":"Comput. J."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Hossain, S., and Mahmud, M.S. (2019, January 24\u201326). On computing with diagonally structured matrices. Proceedings of the 2019 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2019.8916325"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Eagan, J., Herdman, M., Vaughn, C., Bean, N., Kern, S., and Pirouz, M. (2023, January 8\u201311). An Efficient Parallel Divide-and-Conquer Algorithm for Generalized Matrix Multiplication. Proceedings of the 2023 IEEE 13th Annual Computing and Communication Workshop and Conference (CCWC), Las Vegas, NV, USA.","DOI":"10.1109\/CCWC57344.2023.10099141"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Haque, S.A., Choudhury, N., and Hossain, S. (2023, January 17\u201319). Matrix Multiplication with Diagonals: Structured Sparse Matrices and Beyond. Proceedings of the 2023 7th International Conference on High Performance Compilation, Computing and Communications, Jinan, China.","DOI":"10.1145\/3606043.3606053"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Barrachina, S., Castillo, M., Igual, F.D., Mayo, R., and Quintana-Ort\u00ed, E.S. (2008, January 26\u201329). Solving dense linear systems on graphics processors. Proceedings of the European Conference on Parallel Processing, Las Palmas de Gran Canaria, Spain.","DOI":"10.1007\/978-3-540-85451-7_79"},{"key":"ref_24","unstructured":"Volkov, V., and Demmel, J. (2023, December 10). LU, QR and Cholesky Factorizations using Vector Capabilities of GPUs. Available online: https:\/\/bebop.cs.berkeley.edu\/pubs\/volkov2008-gpu-factorizations.pdf."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1109\/TPDS.2018.2791438","article-title":"G-crs: Gpu accelerated cauchy reed-solomon coding","volume":"29","author":"Liu","year":"2018","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Larsen, E.S., and McAllister, D. (2001, January 10\u201316). Fast matrix multiplies using graphics hardware. Proceedings of the 2001 ACM\/IEEE Conference on Supercomputing, Denver, CO, USA.","DOI":"10.1145\/582034.582089"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Barrachina, S., Castillo, M., Igual, F.D., Mayo, R., and Quintana-Orti, E.S. (2008, January 14\u201318). Evaluation and tuning of the level 3 CUBLAS for graphics processors. Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, USA.","DOI":"10.1109\/IPDPS.2008.4536485"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Cui, X., Chen, Y., Zhang, C., and Mei, H. (2010, January 8\u201310). Auto-tuning dense matrix multiplication for GPGPU with cache. Proceedings of the 2010 IEEE 16th International Conference on Parallel and Distributed Systems, Shanghai, China.","DOI":"10.1109\/ICPADS.2010.64"},{"key":"ref_29","unstructured":"Osama, M., Merrill, D., Cecka, C., Garland, M., and Owens, J.D. (March, January 25). Stream-K: Work-Centric Parallel Decomposition for Dense Matrix-Matrix Multiplication on the GPU. Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, Montreal, QC, Canada."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Matam, K., Indarapu, S.R.K.B., and Kothapalli, K. (2012, January 18\u201322). Sparse matrix-matrix multiplication on modern architectures. Proceedings of the 2012 19th International Conference on High Performance Computing, Pune, India.","DOI":"10.1109\/HiPC.2012.6507483"},{"key":"ref_31","unstructured":"Naumov, M., Chien, L., Vandermersch, P., and Kapasi, U. (2010, January 20\u201323). Cusparse library. Proceedings of the GPU Technology Conference, San Jose, CA, USA."},{"key":"ref_32","unstructured":"Bell, N., and Garland, M. (Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph computations, 2012). Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph computations, Version 0.3.0."},{"key":"ref_33","unstructured":"Hoberock, J., and Bell, N. (2023, December 10). Thrust: A Parallel Template Library; GPU Computing Gems Jade Edition, 359; 2011. Available online: https:\/\/shop.elsevier.com\/books\/gpu-computing-gems-jade-edition\/hwu\/978-0-12-385963-1."},{"key":"ref_34","first-page":"776","article-title":"In-place matrix transposition on GPUs","volume":"27","author":"Sung","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1145\/1839676.1839694","article-title":"Understanding throughput-oriented architectures","volume":"53","author":"Garland","year":"2010","journal-title":"Commun. ACM"},{"key":"ref_36","unstructured":"Haque, S.A., Moreno Maza, M., and Xie, N. (2016). Parallel Computing: On the Road to Exascale, IOS Press."},{"key":"ref_37","unstructured":"Davis, T. (2023, January 01). Florida Sparse Matrix Collection. Available online: http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/index.html."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/1\/31\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T13:45:13Z","timestamp":1760103913000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/1\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,12]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,1]]}},"alternative-id":["a17010031"],"URL":"https:\/\/doi.org\/10.3390\/a17010031","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,1,12]]}}}