cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914110460919808 |
|---|---|
| author | Aguirre, Jacob M. Cifuentes, Diego Guigues, Vincent Monteiro, Renato D. C. Nascimento, Victor Hugo Sujanani, Arnesh |
| author_facet | Aguirre, Jacob M. Cifuentes, Diego Guigues, Vincent Monteiro, Renato D. C. Nascimento, Victor Hugo Sujanani, Arnesh |
| contents | This paper introduces cuHALLaR, a GPU-accelerated implementation of the HALLaR method proposed in Monteiro et al. 2024 for solving large-scale semidefinite programming (SDP) problems. We demonstrate how our Julia-based implementation efficiently uses GPU parallelism through optimization of simple, but key, operations, including linear maps, adjoints, and gradient evaluations. Extensive numerical experiments across three SDP problem classes, i.e., maximum stable set, matrix completion, and phase retrieval show significant performance improvements over both CPU implementations and existing GPU-based solvers. For the largest instances, cuHALLaR achieves speedups of 30-140x on matrix completion problems, up to 135x on maximum stable set problems for Hamming graphs with 8.4 million vertices, and 15-47x on phase retrieval problems with dimensions up to 3.2 million. Our approach efficiently handles massive problems with dimensions up to (n,m) equal to (8 million, 300 million) with high precision, solving matrix completion instances with over 8 million rows and columns in just 142 seconds. These results establish cuHALLaR as a very promising GPU-based method for solving large-scale semidefinite programs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13719 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming Aguirre, Jacob M. Cifuentes, Diego Guigues, Vincent Monteiro, Renato D. C. Nascimento, Victor Hugo Sujanani, Arnesh Optimization and Control 90C30, 65K10, 90C26, 90C60, 90C25 This paper introduces cuHALLaR, a GPU-accelerated implementation of the HALLaR method proposed in Monteiro et al. 2024 for solving large-scale semidefinite programming (SDP) problems. We demonstrate how our Julia-based implementation efficiently uses GPU parallelism through optimization of simple, but key, operations, including linear maps, adjoints, and gradient evaluations. Extensive numerical experiments across three SDP problem classes, i.e., maximum stable set, matrix completion, and phase retrieval show significant performance improvements over both CPU implementations and existing GPU-based solvers. For the largest instances, cuHALLaR achieves speedups of 30-140x on matrix completion problems, up to 135x on maximum stable set problems for Hamming graphs with 8.4 million vertices, and 15-47x on phase retrieval problems with dimensions up to 3.2 million. Our approach efficiently handles massive problems with dimensions up to (n,m) equal to (8 million, 300 million) with high precision, solving matrix completion instances with over 8 million rows and columns in just 142 seconds. These results establish cuHALLaR as a very promising GPU-based method for solving large-scale semidefinite programs. |
| title | cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming |
| topic | Optimization and Control 90C30, 65K10, 90C26, 90C60, 90C25 |
| url | https://arxiv.org/abs/2505.13719 |