# Accelerating Low-Rank Factorization-Based Semidefinite Programming Algorithms on GPU

arXiv: https://arxiv.org/abs/2407.15049 · HTML: https://mlsanity.com/paper/2407.15049/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2024.

## Built on by (most cited first, 3 of 3)

- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)
- [Fast SDP certification of neural networks : towards large multi-class datasets](https://mlsanity.com/paper/2607.03232/) (2026)

## Abstract (arXiv)

In this paper, we address a long-standing challenge: how to achieve both efficiency and scalability in solving semidefinite programming problems. We propose breakthrough acceleration techniques for a wide range of low-rank factorization-based first-order methods using GPUs, making the computation much more efficient and scalable. To illustrate the idea and effectiveness of our approach, we use the low-rank factorization-based SDP solver, LoRADS, as an example, which involves both the classic Burer-Monterio method and a novel splitting scheme with a starting logarithmic rank. Our numerical results demonstrate that the accelerated GPU version of LoRADS, cuLoRADS, can solve huge-scale semidefinite programming problems with remarkable efficiency. By effectively leveraging GPU computational power, cuLoRADS exhibits outstanding performance. Specifically, it can solve a set of MaxCut problems with 107 × 107 matrix variables in 10 seconds to 1 minute each on an NVIDIA H100 GPU with 80GB memory, whereas previous solvers demonstrated the capability of handling problems of this scale, required at least dozens of hours per problem on CPUs. Additionally, cuLoRADS shows exceptional scalability by solving 1) a MaxCut problem with a 170  million × 170  million matrix variable and 2) a Matrix Completion problem with a 20 million × 20 million matrix variable and approximately 200 million constraints, both in a matter of minutes.