Skip to content
Preprint

Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs

Sep 2026 · 0 citations · 31 references
Engineering Computer Science Mathematics

TL;DR

A GPU-accelerated direct linear solver for branch MPC formulations in which all trajectories share a single root decision node and evolve independently thereafter is presented, providing a reusable backend for multiple optimization algorithms whose reduced systems have the required symmetric positive-definite structure.

Abstract

Branch model predictive control optimizes multiple future trajectories coupled through shared decisions, with computational demands increasing as the number of scenarios and prediction horizon grow. We present a GPU-accelerated direct linear solver for branch MPC formulations in which all trajectories share a single root decision node and evolve independently thereafter. By operating at the linear-algebra level, the solver provides a reusable backend for multiple optimization algorithms whose reduced systems have the required symmetric positive-definite structure. The solver exploits two levels of parallelism: across scenarios and along each prediction horizon. A tailored variable ordering enables horizon-parallel Cholesky factorization while preserving a single root-tail coupling block per scenario in the factor. Numerical experiments demonstrate substantial speedups over state-of-the-art sparse direct solvers, achieving factorization speedups of up to 6.0$\times$ over cuDSS and 27.6$\times$ over eight-thread PARDISO, with triangular solve speedups of up to 3.5$\times$ and 15.8$\times$, respectively.

View source

Similar papers

Preprint Sep 2026

Distributed Linear Programming on GPU Clusters at Extreme Scale

SHARDLP is presented, a distributed GPU LP solver that keeps the matrix and primal-dual state partitioned from sharded input through solution output and reaches the published criterion on nine of eleven instances, on the Google PDLP benchmark.

Arnaud Deza, S. Dey, P. Van Hentenryck · 1 citation
#machine learning Preprint Sep 2026

GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra

This paper introduces rlaopt, a PyTorch-based package for large-scale optimization and scientific computing using randomized numerical linear algebra (RandNLA). Despite substantial progress in RandNLA-based algorithms, few implementations combine GPU acceleration with a simple interface for specifying optimization prob...

Pratik Rathore, Zachary Frangella, P. Nobel et al. · 0 citations
Preprint Sep 2026

Accelerating massive ensembles of ordinary differential equations

Solving large ensembles of small, independent ordinary differential equations (ODEs) is a common task in computational science and engineering, arising for example in Bayesian parameter estimation, Monte Carlo uncertainty quantification, and the integration of uncoupled physical systems such as the linearised Einstein-...

Lawrence Berry, Will Handley, Oliver Hahn et al. · 1 citation
#artificial intelligence Preprint Sep 2026

MeanField Surrogate Modeling for Scalable Runtime Scheduling of Concurrent Heterogeneous AI Inference on Shared GPUs

A MeanField surrogate is proposed that predicts per-model performance from local configuration and aggregate GPU state rather than explicitly modeling all joint interactions, showing high predictive accuracy and empirical sample budget that grows approximately linearly in $N, in contrast to the combinatorial cost of fu...

Youssef Ennouri, Soonhoi Ha · 0 citations
Open access Sep 2026

PERFORMANCE COMPARISON OF EXPLICIT EULER IMPLEMENTATIONS FOR AN ENSEMBLE OF RUCKLIDGE SYSTEM TRAJECTORIES IN MATLAB

Large-scale integration of independent trajectories of dynamic system is limited not only by the cost of the recurrence step but also by the organization of parallel work, storage of intermediate states, and transfers between memory levels. This study compares explicit Euler implementations for an ensemble of Rucklidge...

Oleksandr Razovyi, Oleg Golevych · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.