What it is
Semidefinite programming (SDP) is a powerful framework used across optimization, machine learning and quantum computing, but solving large problems has been costly. The authors co-design low-rank algorithms with GPU hardware in cuLoRADS, a solver that combines the Burer-Monteiro method with a splitting scheme, and report gains of up to four orders of magnitude in speed and scalability for large SDPs with sparse and low-rank structure. On an NVIDIA H100 GPU with 80 GB of memory it solves a set of MaxCut problems in 10 seconds to a minute each, where previously reported CPU solvers needed dozens of hours, and it solves still larger MaxCut and minimum-rank matrix completion problems in minutes.
Why it matters
The computational cost of large-scale SDP has been a long-standing practical limit on its use. Beyond speed, the solver resolves a long-standing SDP computational barrier in the quantum ordered search problem, which the authors report had remained unsolved for 18 years.
Every metric behind this entry is listed, with its source, under Sources and data below.
Filed underAdvanced Optimization Algorithms Research, Stochastic Gradient Optimization Techniques, Sparse and Compressive Sensing Techniques