Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs
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× over cuDSS and 27.6× over eight-thread PARDISO, with triangular solve speedups of up to 3.5× and 15.8×, respectively.
Related
- A comparison of parallel iterative methods for ILU triangular solves
- Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
- Direct proofs for spaces with cyclic parallel Ricci tensor
- Space-Time Parallel Direct Numerical Simulation of Rayleigh-Bénard Convection
- A Massively Parallel Hybridizable Discontinuous Galerkin Solver for Direct Numerical Simulation of Compressible Flows on GPUs
BibTeX
@misc{song2026accelerating,
title = {{Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs}},
author = {Fenglong Song and Luyao Zhang and Liang Wu and Ján Drgoňa and Colin N. Jones},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29977},
eprint = {2609.29977},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29977},
}
RIS
TY - UNPB
TI - Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs
AU - Fenglong Song
AU - Luyao Zhang
AU - Liang Wu
AU - Ján Drgoňa
AU - Colin N. Jones
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29977
UR - https://arxiv.org/abs/2609.29977
AB - 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× over cuDSS and 27.6× over eight-thread PARDISO, with triangular solve speedups of up to 3.5× and 15.8×, respectively.
ER -