{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T19:55:49Z","timestamp":1790625349827,"version":"4.1.0"},"reference-count":58,"publisher":"National Academy of Sciences","issue":"40","license":[{"start":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T00:00:00Z","timestamp":1790553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"MOST | National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72225009"],"award-info":[{"award-number":["72225009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"MOST | National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72394360"],"award-info":[{"award-number":["72394360"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"MOST | National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72394365"],"award-info":[{"award-number":["72394365"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"MOST | National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72394363"],"award-info":[{"award-number":["72394363"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"MOST | National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72394360"],"award-info":[{"award-number":["72394360"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"MOST | National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12122107"],"award-info":[{"award-number":["12122107"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Natural Science Foundation of Shanghai","award":["24ZR1421300"],"award-info":[{"award-number":["24ZR1421300"]}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2026,10,6]]},"abstract":"\n Semidefinite programming (SDP) provides a powerful framework in applied mathematics with applications spanning optimization, machine learning, quantum computing, and beyond. However, the computational cost of solving large-scale SDP problems remains a significant practical limitation. We break this long-standing computational bottleneck through a synergistic codesign of low-rank algorithms and graphics processing unit (GPU) architectures, developing accelerated first-order methods that leverage both algorithmic innovations and hardware-aware implementation to achieve up to 4 orders of magnitude improvements in speed and scalability for large-scale SDPs with sparse and low-rank structure, thereby opening frontiers in large-scale scientific computing. Our solver, GPU-accelerated Low-Rank Alternating Direction Method of Multipliers Splitting (cuLoRADS), exemplifies this approach, combining the Burer-Monteiro method with a splitting scheme to efficiently solve massive-scale SDPs. Specifically, it can solve a set of MaxCut problems whose matrix variables have dimensions of\n \n \n \n \n 10<\/mml:mn>\n 7<\/mml:mn>\n <\/mml:msup>\n \u00d7<\/mml:mo>\n \n 10<\/mml:mn>\n 7<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:inline-formula>\n in 10 s to 1 min each on an NVIDIA H100 GPU with 80 GB of memory, whereas previously reported central processing unit solvers required dozens of hours. Additionally, cuLoRADS shows exceptional scalability by solving 1) a MaxCut problem with a\n \n \n \n 170<\/mml:mn>\n \n million<\/mml:mtext>\n \u00d7<\/mml:mo>\n 170<\/mml:mn>\n \n million<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:inline-formula>\n matrix variable and 2) a Minimum-Rank Matrix Completion problem with a\n \n \n 20<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>\n million\n \n \n \u00d7<\/mml:mo>\n <\/mml:math>\n <\/jats:inline-formula>\n 20 million matrix variable and approximately\n \n \n 200<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>\n million constraints, both in a matter of minutes. It also resolves a long-standing SDP computational barrier in the quantum ordered search problem, which had remained unsolved for 18 y.\n <\/jats:p>","DOI":"10.1073\/pnas.2516128123","type":"journal-article","created":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T19:02:56Z","timestamp":1790622176000},"update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":0,"title":["Large-scale semidefinite programming with graphics processing units"],"prefix":"10.1073","volume":"123","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-2271-0455","authenticated-orcid":false,"given":"Qiushi","family":"Han","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/047426m28","id-type":"ROR","asserted-by":"publisher"}],"name":"Department of Computer Science, University of Illinois at Urbana-Champaign","place":["Urbana"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9960-964X","authenticated-orcid":false,"given":"Zhenwei","family":"Lin","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00wtvfq62","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Information Management and Engineering, Shanghai University of Finance and Economics","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanwen","family":"Liu","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/047426m28","id-type":"ROR","asserted-by":"publisher"}],"name":"Department of Electrical & Computer Engineering, University of Illinois at Urbana-Champaign","place":["Urbana"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8057-3690","authenticated-orcid":false,"given":"Caihua","family":"Chen","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01rxvg760","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Management and Engineering, Nanjing University, Nanjing","place":["Jiangsu, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5164-5269","authenticated-orcid":false,"given":"Qi","family":"Deng","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0220qvk04","id-type":"ROR","asserted-by":"publisher"}],"name":"Antai College of Economics and Management, Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9328-527X","authenticated-orcid":false,"given":"Dongdong","family":"Ge","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0220qvk04","id-type":"ROR","asserted-by":"publisher"}],"name":"Antai College of Economics and Management, Shanghai Jiao Tong University","place":["Shanghai, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00f54p054","id-type":"ROR","asserted-by":"publisher"}],"name":"Department of Management Science and Engineering, Stanford University","place":["Stanford"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2026,9,28]]},"reference":[{"key":"e_1_3_4_1_2","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_4_2_2","first-page":"1","article-title":"Semidefinite relaxations, multivariate normal distributions, and order statistics","volume":"3","author":"Bertsimas D.","year":"1998","unstructured":"D. Bertsimas, Y. Ye, Semidefinite relaxations, multivariate normal distributions, and order statistics. Handb. Comb. Optim. 3, 1\u201319 (1998).","journal-title":"Handb. Comb. Optim."},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.75.032335"},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","unstructured":"A. E. DePrince III Variational determination of the two-electron reduced density matrix: A tutorial review. WIREs Comput. Mol. Sci. 14 e1702 (2024).","DOI":"10.1002\/wcms.1702"},{"key":"e_1_3_4_6_2","doi-asserted-by":"crossref","unstructured":"G. H. Low Fast quantum simulation of electronic structure by spectral amplification. Phys. Rev. X 15 041016 (2025).","DOI":"10.1103\/pb2g-j9cw"},{"key":"e_1_3_4_7_2","unstructured":"P. Parrilo \u201cStructured semidenite programs and semialgebraic geometry methods in robustness and optimization \u201d PhD thesis California Institute of Technology (2000)."},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","unstructured":"A. Papachristodoulou S. Prajna \u201cA tutorial on sum of squares techniques for systems analysis\u201d in Proceedings of the 2005 American Control Conference (IEEE 2005) vol. 4 pp. 2686\u20132700.","DOI":"10.1109\/ACC.2005.1470374"},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","unstructured":"E. J. Cand\u00e8s B. Recht Exact matrix completion via convex optimization. Found. Comput. Math. 9 717\u2013772 (2009).","DOI":"10.1007\/s10208-009-9045-5"},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","unstructured":"A. d\u2019Aspremont L. El Ghaoui M. I. Jordan G. R. G. Lanckriet A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49 434\u2013448 (2007).","DOI":"10.1137\/050645506"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2011.2160974"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2017.1288729"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2014.2309732"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2014.2323634"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0040-1"},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","unstructured":"P. Biswas Y. Ye \u201cSemidefinite programming for ad hoc wireless sensor network localization\u201d in Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks IPSN \u201904 K. Ramchandran J. Sztipanovits J. C. Hou T. N. Pappas Eds. (Association for Computing Machinery New York NY 2004) pp. 46\u201354.","DOI":"10.1145\/984622.984630"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/05062754X"},{"key":"e_1_3_4_18_2","unstructured":"M. Grant S. Boyd Y. Ye Cvx users\u2019 guide (2009)."},{"key":"e_1_3_4_19_2","first-page":"1","article-title":"Cvxpy: A python-embedded modeling language for convex optimization","volume":"17","author":"Diamond S.","year":"2016","unstructured":"S. Diamond, S. Boyd, Cvxpy: A python-embedded modeling language for convex optimization. J. Mach. Learn. Res. 17, 1\u20135 (2016).","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_4_20_2","doi-asserted-by":"crossref","unstructured":"J. L\u00f6fberg \u201cYALMIP: A toolbox for modeling and optimization in MATLAB\u201d in Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design (IEEE 2004) pp. 284\u2013289.","DOI":"10.1109\/CACSD.2004.1393890"},{"key":"e_1_3_4_21_2","unstructured":"F. Alizadeh-Dehkharghani \u201cCombinatorial optimization with interior point methods and semidefinite matrices \u201d PhD thesis University of Minnesota (1991). https:\/\/www.proquest.com\/dissertations-theses\/combinatorial-optimization-with-interior-point\/docview\/303943307\/se-2."},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032701"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0017-1"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0261-6"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-0892-3"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/080718206"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0082-6"},{"key":"e_1_3_4_30_2","doi-asserted-by":"crossref","unstructured":"Q. Han et al. A low-rank ADMM splitting approach for semidefinite programming. arXiv [Preprint] (2024). https:\/\/doi.org\/10.48550\/arXiv.2403.09133.","DOI":"10.1287\/ijoc.2024.0701"},{"key":"e_1_3_4_31_2","doi-asserted-by":"crossref","unstructured":"R. D. C. Monteiro A. Sujanani D. Cifuentes A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach. Math. Program 10.1007\/s10107-026-02338-0 (2026).","DOI":"10.1007\/s10107-026-02338-0"},{"key":"e_1_3_4_32_2","doi-asserted-by":"crossref","unstructured":"B. Yal\u00e7in Z. Ma J. Lavaei S. Sojoudi \u201cSemidefinite programming versus burer-monteiro factorization for matrix sensing\u201d in Proceedings of the AAAI Conference on Artificial Intelligence B. Williams Y. Chen J. Neville Eds. (AAAI Press Washington DC 2023) vol. 37 pp. 10702\u201310710.","DOI":"10.1609\/aaai.v37i9.26270"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556780500286582"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01686-3"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.2.339"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574037"},{"key":"e_1_3_4_37_2","unstructured":"A. Krizhevsky I. Sutskever G. E. Hinton \u201cImagenet classification with deep convolutional neural networks\u201d in Advances in Neural Information Processing Systems F. Pereira C. Burges L. Bottou K. Weinberger Eds. (Curran Associates Inc. 2012) vol. 25."},{"key":"e_1_3_4_38_2","unstructured":"N Corporation NVIDIA cuDSS (2025). https:\/\/developer.NVIDIA.com\/cudss. Accessed 26 November 2025."},{"key":"e_1_3_4_39_2","doi-asserted-by":"crossref","unstructured":"Y. Chen D. Tse P. Nobel P. Goulart S. Boyd CuClarabel: GPU acceleration for a conic optimization solver. arXiv [Preprint] (2024). https:\/\/doi.org\/10.48550\/arXiv.2412.19027 (Accessed 11 September 2026).","DOI":"10.1145\/3815420"},{"key":"e_1_3_4_40_2","doi-asserted-by":"crossref","unstructured":"H. Lu J. Yang cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Oper. Res. 73 3440\u20133452 (2025).","DOI":"10.1287\/opre.2024.1069"},{"key":"e_1_3_4_41_2","unstructured":"H. Lu et al. cuPDLP-C: A strengthened implementation of cuPDLP for linear programming by C language. arXiv [Preprint] (2024). https:\/\/doi.org\/10.48550\/arXiv.2312.14832."},{"key":"e_1_3_4_42_2","doi-asserted-by":"crossref","unstructured":"Y. Huang Restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming. arXiv [Preprint] (2024). https:\/\/doi.org\/10.48550\/arXiv.2405.16160.","DOI":"10.1287\/ijoc.2024.0983"},{"key":"e_1_3_4_43_2","doi-asserted-by":"crossref","unstructured":"H. Lu J. Yang A practical and optimal first-order method for large-scale convex quadratic programming. Math. Program. 215 771\u2013808 (2026).","DOI":"10.1007\/s10107-025-02241-0"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118723203"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"e_1_3_4_46_2","doi-asserted-by":"crossref","unstructured":"W. Gao D. Ge Y. Ye Algorithm 1055: HDSDP: Software for semidefinite programming. ACM Trans. Math. Softw. 51 30 (2025).","DOI":"10.1145\/3721123"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"key":"e_1_3_4_48_2","unstructured":"D. Ge Q. Huangfu Z. Wang J. Wu Y. Ye Cardinal Optimizer (COPT) User Guide version 6.0.1 (Cardinal Operations 2022). arXiv [Preprint] (2022). https:\/\/doi.org\/10.48550\/arXiv.2208.14314."},{"key":"e_1_3_4_49_2","unstructured":"Y. Ye Gset [Data set] (2003). https:\/\/web.stanford.edu\/~yyye\/yyye\/Gset\/. Accessed 11 September 2026."},{"key":"e_1_3_4_50_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2049662.2049663","article-title":"The university of Florida sparse matrix collection","volume":"38","author":"Davis T. A.","year":"2011","unstructured":"T. A. Davis, Y. Hu, The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1\u201325 (2011).","journal-title":"ACM Trans. Math. Softw."},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-025-02952-8"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1305045"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_29"},{"key":"e_1_3_4_54_2","unstructured":"E. Farhi J. Goldstone S. Gutmann M. Sipser Invariant quantum algorithms for insertion into an ordered list. arXiv [Preprint] (1999). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/9901059."},{"key":"e_1_3_4_55_2","unstructured":"B. Jacokes \u201cAn improved quantum algorithm for searching an ordered list\u201d in Research Science Institute Student Reports 2003 C. C. Mihelich Ed. (Center for Excellence in Education Vienna VA 2003) pp. 19\u201326."},{"key":"e_1_3_4_56_2","doi-asserted-by":"crossref","unstructured":"J. Carolan A. M. Childs M. Kovacs-Deak L. Schaeffer Translation-invariant quantum algorithms for ordered search are optimal. arXiv [Preprint] (2025). https:\/\/doi.org\/10.48550\/arXiv.2503.21090.","DOI":"10.1145\/3800579"},{"key":"e_1_3_4_57_2","unstructured":"Y. E. Nesterov M. J. Todd Y. Ye \u201cInfeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems\u201d (Tech. Rep. 1156 Cornell University Operations Research and Industrial Engineering 1996)."},{"key":"e_1_3_4_58_2","unstructured":"Y. Wu \u201cMatrix-free GPU semidefinite programming for quantum ordered search at the k = 6 frontier\u201d in Proceedings of the 43rd International Conference on Machine Learning (PMLR 2026)."}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.2516128123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T19:04:29Z","timestamp":1790622269000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/10.1073\/pnas.2516128123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,28]]},"references-count":58,"journal-issue":{"issue":"40","published-print":{"date-parts":[[2026,10,6]]}},"alternative-id":["10.1073\/pnas.2516128123"],"URL":"https:\/\/doi.org\/10.1073\/pnas.2516128123","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9,28]]},"assertion":[{"value":"2025-06-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-09-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e2516128123"}}