BCHOL

BCHOL

A GPU-accelerated implementation of the sparse linear system solver described in rsLQR. Designed for optimal control, BCHOL exploits the structure of the LQR problem with recursive application of Schur complements, achieving a time complexity of $O(log(N))$.

• src/solver.cu: CUDA kernels and C++ solver API
• src/bchol.hpp: solver interface (used by pybind11)
• src/bchol_core.cuh: hierarchical Cholesky factorization device functions
• src/math.cuh: math device functions
• src/debug.cuh: debug utils
• configs/robots.yaml: robotics-sized problem presets
• python/bindings.cpp: pybind11 extensions
• python/sweep.py: benchmarking across problem sizes and horizons
• python/linsys.py: KKT linear system
• examples/solve_linsys.cpp: minimal C++ example
• examples/bchol.ipynb: Python demo notebook

For further documentation please refer to Yana Botvinnik's notes and Python implementation.

Setup

BCHOL works with:

• CUDA 12.6
• C++17
• gcc 11.4.0
• CMake 3.22
• Python 3.10.12

uv sync
cmake -S . -B build \
  -DBCHOL_N=8 \          # horizon
  -DBCHOL_NX=12 \        # state size
  -DBCHOL_NU=4 \         # control size
  -DBCHOL_CUDA_ARCH=89 \
  -DCMAKE_BUILD_TYPE=Release

CMake options

• BCHOL_N, BCHOL_NX, BCHOL_NU: compile-time problem dimensions
• BCHOL_CUDA_ARCH: CUDA compute capability
• BCHOL_USE_FAST_MATH: ON by default
• BCHOL_MAXRREG: optional register cap for CUDA
• BCHOL_BUILD_PYBIND, BCHOL_BUILD_EXAMPLES, BCHOL_BUILD_TESTS
• BCHOL_PYBIND_MODULE_NAME: module name for pybind11 target (default: bchol_ext)
• BCHOL_PYBIND_OUTPUT_DIR: output dir for pybind11 module (default: python/ext)

Build (bindings + example)

cmake --build build -j
./build/solve_linsys       # C++ example

Python bindings

• Specify problem size and horizon in configs/robots.yaml
• Modules are emitted to python/ext/ as bchol_ext_N*_nx*_nu*.so
• Use ./build_all.sh or python/sweep.py to build multiple configs

./build_all.sh

# or

uv run python/sweep.py --config-yaml configs/robots.yaml

---

Import and instantiate:

from linsys import make_solver
solver = make_solver("bchol_ext_N32_nx12_nu4")

The solver class BCHOL exposes:

• Properties:
  • nhorizon, nstates, ninputs
  • q_r_dense_size, q_r_rhs_size, a_b_size, d_size, soln_size
• Methods:
  • solve(Q_R, q_r, A_B, d) -> (sol, solve_ms) - allocates output
  • solve_into(Q_R, q_r, A_B, d, out) -> solve_ms - reuses output buffer

solve_into() is preferred for repeated solves since it avoids output allocation.

Related

• GATO: GPU-accelerated batched trajectory optimization for real-time optimal control.
• GBD-PCG: Parallel preconditioned conjugate gradient solver for block-tridiagonal linear systems.
• GRiD: GPU-accelerated rigid body dynamics with analytical gradients.