Pith. sign in

REVIEW 8 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2407.15049 v3 pith:4AOARMB5 submitted 2024-07-21 math.OC

Qiushi Han , Zhenwei Lin , Hanwen Liu , Caihua Chen , Qi Deng , Dongdong Ge , Yinyu Ye This is my paper · ORCID
classification math.OC
keywords millionmatrixproblemsculoradsfactorization-basedlow-rankproblemprogramming
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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 $10^7 \times 10^7$ 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 \text{ million} \times 170 \text{ million}$ matrix variable and 2) a Matrix Completion problem with a 20 million $\times$ 20 million matrix variable and approximately 200 million constraints, both in a matter of minutes.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 8 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs

    math.OC 2026-07 conditional novelty 7.0 of 10

    CARDAL grows the rank of a Burer–Monteiro factorization only when dual-slack curvature is negative and distributes the resulting low-rank augmented-Lagrangian solver across GPUs.

  2. New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming

    math.OC 2025-05 conditional novelty 7.0 of 10

    Augmented Lagrangian subproblems inherit low-rankness, strict complementarity, and quadratic growth from a primal simple SDP, making Burer-Monteiro gradient descent converge linearly.

  3. Input-to-state Stable Approximate Nonlinear Model Predictive Control with Realtime Feasibility

    eess.SY 2026-07 accept novelty 6.0 of 10

    A precomputed ISS-CLF/robust-CBF pair yields a real-time QP that approximates robust NMPC with proven ISS and constraint satisfaction for nonlinear systems.

  4. Fast SDP certification of neural networks : towards large multi-class datasets

    math.CO 2026-07 conditional novelty 6.0 of 10

    An untargeted SDP relaxation certifies full multi-class ReLU robustness in a single solve, with stable-active neuron pruning that shrinks the matrices and accelerates convergence.

  5. Solving Imperfect-Recall Games via Sum-of-Squares Optimization

    cs.GT 2026-02 conditional novelty 6.0 of 10

    Moment-SOS hierarchies provably compute behavioral optima/equilibria in imperfect-recall games, with exact convergence at level ℓ+1 for non-absentminded single-player games.

  6. PDHCG: A Scalable First-Order Method for Large-Scale Competitive Market Equilibrium Computation

    math.OC 2025-06 conditional novelty 6.0 of 10

    A restarted primal-dual method with a per-buyer bisection inner solve, run on GPUs, computes Fisher equilibria at ten-million-buyer scale and extends to Arrow-Debreu markets via fixed-point iteration.

  7. Scalable First-order Method for Certifying Optimal k-Sparse GLMs

    cs.LG 2025-02 conditional novelty 6.0 of 10

    A FISTA-based method with a custom PAVA computes perspective-relaxation dual bounds for k-sparse GLMs in O(p log p) per prox evaluation, enabling larger optimality certificates.

  8. An Overview of GPU-based First-Order Methods for Linear Programming and Extensions

    math.OC 2025-06 unverdicted novelty 2.0 of 10

    A survey of GPU-based first-order LP solvers focusing on cuPDLP, its PDHG core, theory, benchmarks, and extensions to QP, SDP, and conic programming.

Pith tools