{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T19:26:21Z","timestamp":1775244381845,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T00:00:00Z","timestamp":1748217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T00:00:00Z","timestamp":1748217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"crossref","award":["201807000143"],"award-info":[{"award-number":["201807000143"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Region Grand-Est"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2025,8]]},"DOI":"10.1007\/s10766-025-00799-y","type":"journal-article","created":{"date-parts":[[2025,5,26]],"date-time":"2025-05-26T03:44:07Z","timestamp":1748231047000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Generating Sparse Matrices for Large-Scale Spectral Clustering on a Single GPU"],"prefix":"10.1007","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3753-3671","authenticated-orcid":false,"given":"Guanlin","family":"He","sequence":"first","affiliation":[]},{"given":"St\u00e9phane","family":"Vialle","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Baboulin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,26]]},"reference":[{"issue":"6","key":"799_CR1","doi-asserted-by":"publisher","first-page":"1550","DOI":"10.1109\/TPDS.2016.2630699","volume":"28","author":"HM Aktulga","year":"2017","unstructured":"Aktulga, H.M., Afibuzzaman, M., Williams, S., et al.: A high performance block Eigensolver for nuclear configuration interaction calculations. IEEE Trans. Parallel Distrib. Syst. 28(6), 1550\u20131563 (2017)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"799_CR2","doi-asserted-by":"crossref","unstructured":"Anastasiu, D.C., Karypis, G.: L2knng: fast exact k-nearest neighbor graph construction with l2-norm pruning. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 791\u2013800, (2015)","DOI":"10.1145\/2806416.2806534"},{"key":"799_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.jpdc.2017.11.016","volume":"129","author":"DC Anastasiu","year":"2019","unstructured":"Anastasiu, D.C., Karypis, G.: Parallel cosine nearest neighbor graph construction. J. Parallel Distrib. Comput. 129, 61\u201382 (2019)","journal-title":"J. Parallel Distrib. Comput."},{"key":"799_CR4","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA (2007)"},{"key":"799_CR5","unstructured":"Bell, N., Garland, M.: Efficient sparse matrix-vector multiplication on CUDA. Technical report, Nvidia Technical Report NVR-2008-004, Nvidia Corporation (2008)"},{"issue":"10","key":"799_CR6","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2347736.2347755","volume":"55","author":"P Domingos","year":"2012","unstructured":"Domingos, P.: A few useful things to know about machine learning. Commun. ACM 55(10), 78\u201387 (2012)","journal-title":"Commun. ACM"},{"key":"799_CR7","doi-asserted-by":"crossref","unstructured":"Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proceedings of the 20th International Conference on World Wide Web, pp. 577\u2013586 (2011)","DOI":"10.1145\/1963405.1963487"},{"key":"799_CR8","unstructured":"Fender, A.: Parallel solutions for large-scale eigenvalue problems arising in graph analytics. Ph.D. Thesis, Universit\u00e9 Paris-Saclay (2017)"},{"key":"799_CR9","doi-asserted-by":"publisher","first-page":"2338","DOI":"10.1016\/j.procs.2016.05.435","volume":"80","author":"A Fender","year":"2016","unstructured":"Fender, A., Emad, N., et al.: Accelerated hybrid approach for spectral problems arising in graph analytics. Proc. Comput. Sci. 80, 2338\u20132347 (2016)","journal-title":"Proc. Comput. Sci."},{"key":"799_CR10","doi-asserted-by":"crossref","unstructured":"Gao, J., Qi, P., He, G., et\u00a0al.: Efficient CSR-based sparse matrix-vector multiplication on GPU. Math. Probl. Eng. (2016)","DOI":"10.1155\/2016\/4596943"},{"key":"799_CR11","doi-asserted-by":"crossref","unstructured":"Greathouse, J.L., Daga, M.: Efficient sparse matrix-vector multiplication on GPUs using the CSR storage format. In: SC\u201914: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, pp. 769\u2013780, (2014)","DOI":"10.1109\/SC.2014.68"},{"key":"799_CR12","unstructured":"Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., et\u00a0al.: Fast approximate nearest-neighbor search with k-nearest neighbor graph. In: Twenty-Second International Joint Conference on Artificial Intelligence (2011)"},{"key":"799_CR13","unstructured":"He, G.: Parallel algorithms for clustering large datasets on CPU-GPU heterogeneous architectures. Theses, Universit\u00e9 Paris-Saclay, https:\/\/theses.hal.science\/tel-04114475 (2022)"},{"issue":"14","key":"799_CR14","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.6621","volume":"34","author":"G He","year":"2022","unstructured":"He, G., Vialle, S., Baboulin, M.: Parallel and accurate k-means algorithm on CPU\u2013GPU architectures for spectral clustering. Concurr. Comput. Pract. Exp. 34(14), e6621 (2022)","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"799_CR15","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-030-93571-9_4","volume-title":"Network and Parallel Computing","author":"G He","year":"2022","unstructured":"He, G., Vialle, S., Sylvestre, N., et al.: Scalable algorithms using sparse storage for parallel spectral clustering on GPU. In: C\u00e9rin, C., Qian, D., Gaudiot, J.L., et al. (eds.) Network and Parallel Computing, pp. 40\u201352. Springer, Cham (2022)"},{"key":"799_CR16","unstructured":"Ina, T., Hashimoto, A., Iiyama, M., et\u00a0al.: Outlier cluster formation in spectral clustering. arXiv preprint arXiv:1703.01028 (2017)"},{"issue":"8","key":"799_CR17","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"AK Jain","year":"2010","unstructured":"Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recognit. Lett. 31(8), 651\u2013666 (2010)","journal-title":"Pattern Recognit. Lett."},{"key":"799_CR18","doi-asserted-by":"crossref","unstructured":"Jin, Y., J\u00e1J\u00e1, J.F.: A high performance implementation of spectral clustering on CPU-GPU platforms. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshops, Chicago, IL, USA, pp. 825\u2013834, (2016)","DOI":"10.1109\/IPDPSW.2016.79"},{"issue":"2","key":"799_CR19","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1137\/S1064827500366124","volume":"23","author":"AV Knyazev","year":"2001","unstructured":"Knyazev, A.V.: Toward the optimal preconditioned Eigensolver: locally optimal block preconditioned conjugate gradient method. SIAM J. Sci. Comput. 23(2), 517\u2013541 (2001)","journal-title":"SIAM J. Sci. Comput."},{"key":"799_CR20","doi-asserted-by":"crossref","unstructured":"Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4) (2007)","DOI":"10.1007\/s11222-007-9033-z"},{"key":"799_CR21","unstructured":"MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp. 281\u2013297, (1967)"},{"key":"799_CR22","unstructured":"Naumov, M., Moon, T.: Parallel spectral graph partitioning. Technical report, NVIDIA Technical Report, NVR-2016-001 (2016)"},{"issue":"5","key":"799_CR23","doi-asserted-by":"publisher","first-page":"S602","DOI":"10.1137\/140980260","volume":"37","author":"M Naumov","year":"2015","unstructured":"Naumov, M., Arsaev, M., Castonguay, P., et al.: AmgX: A library for GPU accelerated algebraic multigrid and preconditioned iterative methods. SIAM J. Sci. Comput. 37(5), S602\u2013S626 (2015)","journal-title":"SIAM J. Sci. Comput."},{"key":"799_CR24","unstructured":"Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3\u20138, 2001, Vancouver, British Columbia, Canada], pp. 849\u2013856, (2001)"},{"key":"799_CR25","unstructured":"NVIDIA: NVGRAPH Library User\u2019s Guide (DU-08010-001_v10.2). https:\/\/docs.nvidia.com\/pdf\/nvGRAPH_Library.pdf (2019)"},{"key":"799_CR26","unstructured":"NVIDIA: cuSOLVER Library (DU-06709-001_v12.0). https:\/\/docs.nvidia.com\/cuda\/cusolver\/index.html (2022a)"},{"key":"799_CR27","unstructured":"NVIDIA: cuSPARSE Library (DU-06709-001_v12.0). https:\/\/docs.nvidia.com\/cuda\/cusparse\/index.html (2022b)"},{"key":"799_CR28","unstructured":"NVIDIA: CUDA C++ Best Practices Guide (Release 12.2). https:\/\/docs.nvidia.com\/cuda\/cuda-c-best-practices-guide\/index.html (2023a)"},{"key":"799_CR29","unstructured":"NVIDIA: Thrust (Release 12.2). https:\/\/docs.nvidia.com\/cuda\/thrust\/index.html (2023b)"},{"key":"799_CR30","unstructured":"NVIDIA: NVPL Storage Formats. https:\/\/docs.nvidia.com\/nvpl\/_static\/sparse\/storage_format\/sparse_matrix.html (2024)"},{"key":"799_CR31","unstructured":"RAPIDS Development Team: RAPIDS: Libraries for End to End GPU Data Science. https:\/\/rapids.ai (2023)"},{"issue":"5","key":"799_CR32","doi-asserted-by":"publisher","first-page":"S412","DOI":"10.1137\/15M1026419","volume":"38","author":"K Rupp","year":"2016","unstructured":"Rupp, K., Tillet, P., Rudolf, F., et al.: ViennaC\u2014linear algebra library for multi-and many-core architectures. SIAM J. Sci. Comput. 38(5), S412\u2013S439 (2016)","journal-title":"SIAM J. Sci. Comput."},{"key":"799_CR33","doi-asserted-by":"crossref","unstructured":"Saad, Y.: Numerical methods for large eigenvalue problems: Revised edition. SIAM (2011)","DOI":"10.1137\/1.9781611970739"},{"key":"799_CR34","doi-asserted-by":"crossref","unstructured":"Sgherzi, F., Parravicini, A., Santambrogio, M.D.: A mixed precision, multi-GPU design for large-scale Top-K sparse eigenproblems. In: 2022 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1259\u20131263, (2022)","DOI":"10.1109\/ISCAS48785.2022.9937893"},{"key":"799_CR35","doi-asserted-by":"crossref","unstructured":"Sundaram, N., Keutzer, K.: Long term video segmentation through pixel level spectral clustering on GPUs. In: IEEE International Conference on Computer Vision Workshops, ICCV 2011 Workshops, Barcelona, Spain, (2011)","DOI":"10.1109\/ICCVW.2011.6130281"},{"issue":"5 &6","key":"799_CR36","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.parco.2009.12.005","volume":"36","author":"S Tomov","year":"2010","unstructured":"Tomov, S., Dongarra, J., Baboulin, M.: Towards dense linear algebra for hybrid GPU accelerated manycore systems. Parallel Comput. 36(5 &6), 232\u2013240 (2010)","journal-title":"Parallel Comput."},{"key":"799_CR37","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh, N.X., Epps, J., Bailey, J.: Information theoretic measures for Clusterings comparison: variants, properties, normalization and correction for chance. J. Mach. Learn. Res. 11, 2837\u20132854 (2010)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"799_CR38","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.patcog.2007.07.023","volume":"41","author":"T Xiang","year":"2008","unstructured":"Xiang, T., Gong, S.: Spectral clustering with eigenvector selection. Pattern Recognit. 41(3), 1012\u20131029 (2008)","journal-title":"Pattern Recognit."},{"key":"799_CR39","doi-asserted-by":"crossref","unstructured":"Yan, D., Huang, L., Jordan, M.I.: Fast approximate spectral clustering. In: Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, Paris, France, (2009)","DOI":"10.1145\/1557019.1557118"},{"key":"799_CR40","doi-asserted-by":"crossref","unstructured":"Yang, X., Deng, C., Zheng, F., et\u00a0al.: Deep spectral clustering using dual autoencoder network. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 4066\u20134075, (2019)","DOI":"10.1109\/CVPR.2019.00419"},{"key":"799_CR41","unstructured":"Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Advances in Neural Information Processing Systems 17 (NIPS 2004), December 13\u201318, 2004, Vancouver, Canada, pp. 1601\u20131608, (2004)"},{"key":"799_CR42","doi-asserted-by":"crossref","unstructured":"Zheng, J., Chen, W., Chen, Y., et\u00a0al.: Parallelization of spectral clustering algorithm on multi-core processors and GPGPU. In: 2008 13th Asia-Pacific Computer Systems Architecture Conference, IEEE, pp. 1\u20138 (2008)","DOI":"10.1109\/APCSAC.2008.4625449"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-025-00799-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-025-00799-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-025-00799-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T15:39:07Z","timestamp":1757173147000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-025-00799-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,26]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["799"],"URL":"https:\/\/doi.org\/10.1007\/s10766-025-00799-y","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,26]]},"assertion":[{"value":"4 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"22"}}