Session: GPU-Accelerated Mathematical Programming (Part II)
Chair: Haihao Lu
Cluster: Computational Software
Talk 1: Recovering sparse DFT on missing signals via interior point method on GPU
Speaker: Alexis Montoison
Abstract: We present a method for recovering a sparse Discrete Fourier Transform (DFT) of a signal that is noisy and potentially incomplete (i.e., containing missing values). The problem is formulated as a penalized least-squares optimization based on the Inverse Discrete Fourier Transform (IDFT) with an $l_1$-penalty term. By transforming the $l_1$-norm into elastic constraints, we make the problem suitable for an interior point method (IPM) approach. Although Krylov methods are not typically used to solve KKT systems arising in IPM due to the ill-conditioning of these systems, we derive a tailored preconditioner to address this issue. Thanks to this dedicated preconditioner and the fact that FFT and IFFT act as linear operators without requiring the explicit materialization of the underlying matrices, KKT systems can be solved efficiently at large scales in a matrix-free manner. Numerical results from a Julia implementation leveraging Krylov.jl, MadNLP.jl, and GPU-based FFT toolkits such as cuFFT and rocFFT demonstrate the scalability of our approach on problems with millions of variables.
Talk 2: MPAX: Mathematical Programming in JAX
Speaker: Zedong Peng
Abstract: We introduce MPAX (Mathematical Programming in JAX), a versatile and efficient toolbox for integrating mathematical programming into machine learning workflows. MPAX implemented the state-of-the-art first-order methods, restarted average primal-dual hybrid gradient and reflected restarted Halpern primal-dual hybrid gradient, to solve linear programming, quadratic programming and optimal transport problems in JAX. It provides native support for hardware accelerations along with features like batch solving, auto-differentiation, and device parallelism. Extensive numerical experiments demonstrate the advantages of MPAX over existing solvers. The solver is available at https://github.com/MIT-Lu-Lab/MPAX.
Talk 3: Accelerating Low-Rank Factorization-Based Semidefinite Programming Algorithms on GPU
Speaker: Qiushi Han
Abstract: In this paper, we address a long-standing challenge: how to achieve both efficiency and scalability in solving semidefinite programming problems. We propose 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 ×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 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.
