Large-scale semidefinite programming with graphics processing units.

Authors

Qiushi Han, Zhenwei Lin, Hanwen Liu, Caihua Chen, Qi Deng, Dongdong Ge, Yinyu Ye

Published in

Proceedings of the National Academy of Sciences of the United States of America. Volume 123. Issue 40. Pages e2516128123. Oct 06, 2026. Epub Sep 28, 2026.

Abstract

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 [Formula: see text] 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 [Formula: see text] matrix variable and 2) a Minimum-Rank Matrix Completion problem with a [Formula: see text] million [Formula: see text] 20 million matrix variable and approximately [Formula: see text] 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.

PMID:
42804647
Bibliographic data and abstract were imported from PubMed on 29 Sep 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.