Large-scale semidefinite programming with graphics processing units

Abstract

Significance Many scientific and engineering fields, including optimization, machine learning, and quantum computing, use semidefinite programming (SDP) to tackle complex problems. Unfortunately, as these problems grow, they rapidly exceed the capabilities of conventional SDP solvers, creating a critical bottleneck. By leveraging the hidden low-rank structure of large SDPs with sparse problem data, we demonstrate that the parallel processing power of modern graphics processing units can substantially accelerate the solution process and enable much larger problems to be solved. This breakthrough removes a long-standing computational barrier, enabling previously impossible experiments and optimizations across diverse areas of science and engineering.