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

📄 arXiv: 2609.29977v1 📥 PDF

作者: Fenglong Song, Luyao Zhang, Liang Wu, Ján Drgoňa, Colin N. Jones

分类: eess.SY, math.OC

发布日期: 2026-09-24

💡 一句话要点

提出GPU加速的分支模型预测控制以解决计算效率问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 分支模型预测控制 GPU加速 线性求解器 计算效率 优化算法

📋 核心要点

  1. 现有的分支模型预测控制方法在处理多个场景和长预测时间范围时，计算效率低下，难以满足实时应用需求。
  2. 本文提出了一种GPU加速的直接线性求解器，通过双重并行性和定制的变量排序，优化了分支MPC的计算过程。
  3. 实验结果表明，该方法在因子分解和三角求解上分别实现了高达6.0倍和15.8倍的加速，显著优于现有的稀疏求解器。

📝 摘要（中文）

分支模型预测控制（Branch MPC）优化多个未来轨迹，这些轨迹通过共享决策节点相互耦合。随着场景数量和预测时间范围的增加，计算需求显著上升。本文提出了一种GPU加速的直接线性求解器，专为共享单一根决策节点的分支MPC设计。该求解器在进行线性代数操作时，提供了可重用的后端支持多种优化算法，且其简化系统具有所需的对称正定结构。通过在场景间和预测时间范围内的双重并行性，该求解器实现了显著的计算加速，实验结果显示其在因子分解和三角求解上分别比现有稀疏直接求解器快6.0倍和27.6倍。

🔬 方法详解

问题定义：本文旨在解决分支模型预测控制中计算效率低下的问题，尤其是在处理多个场景和长预测时间范围时，现有方法面临的计算需求急剧增加的挑战。

核心思路：提出的GPU加速直接线性求解器通过在场景间和预测时间范围内实现双重并行性，优化了计算过程，允许多个优化算法共享同一根决策节点的结构。

技术框架：整体架构包括一个GPU加速的求解器，采用线性代数操作，支持多种优化算法。求解器通过定制的变量排序实现了高效的Cholesky分解，同时保持每个场景的根-尾耦合块。

关键创新：最重要的创新在于双重并行性设计，允许在场景和时间范围内同时进行计算，从而显著提高了求解效率，与传统方法相比，能够处理更复杂的分支MPC问题。

关键设计：求解器的设计中，采用了定制的变量排序以优化Cholesky分解过程，并确保了每个场景的耦合结构，此外，还实现了针对GPU的高效内存管理和计算调度。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果显示，提出的GPU加速求解器在因子分解上比cuDSS快6.0倍，比八线程的PARDISO快27.6倍；在三角求解上，分别实现了3.5倍和15.8倍的加速，展现出显著的性能优势。

🎯 应用场景

该研究的潜在应用领域包括自动驾驶、机器人路径规划和智能制造等领域，能够在实时决策和控制中提供更高的计算效率，推动相关技术的进步与应用。未来，该方法有望在更复杂的动态环境中实现更高效的模型预测控制，提升系统的智能化水平。

📄 摘要（原文）

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.