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.

Recursive Schur complement tree over an 8-step horizon
Illustration: the horizon is split recursively, so each level of the tree is solved in parallel and the number of sequential steps grows with log N instead of N.

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.

← Back to work