BCHOL
A GPU-Accelerated LQR Solver Using Recursively Applied Schur Complements
Research @ A2R Lab, Columbia University
CUDA · C++17 · pybind11
BCHOL is a GPU implementation of the sparse linear system solver described in rsLQR. It is designed for optimal control: instead of factorizing the LQR problem sequentially over the horizon, it exploits the problem's structure by recursively applying Schur complements, which brings the time complexity down to O(log N) in the horizon length.
Implementation
The solver is written as CUDA kernels with a C++ API, built around hierarchical Cholesky factorization device functions. Problem dimensions (horizon, state size, and control size) are compile-time parameters, so each robot-sized configuration gets its own specialized build. Python bindings expose the solver for benchmarking and experiments, including sweeps across problem sizes and horizons.
Related
BCHOL sits alongside the lab's other GPU-accelerated optimal control tools, including GATO for batched trajectory optimization. It builds on Yana Botvinnik's notes and Python implementation.