BCHOL - Block Cholesky implementation in CUDA

Contains the CUDA accelerated code of the Recursive Schur LQR algorithm. The original C implementation can be found here

Python implementation of the code can be found here

Table of Contents

1. Introduction
2. Requirements
3. Installation
4. Usage
5. Documentation
6. Citing

Introduction

Solves for x in Ax = b, using the Recursive Schur Linear Quadratic Regulator explained in the paper A Parallell Linear System Solver for Optimal Control by Brian E.Jackson. It requires A to be a positive semi-definite matrix to guarantee a good result.

This method is part of the GATO solver (GPU Accelerated Trajectory Optimization) algorithms and model predictive control (MPC). Learn more about GATO here.

Requirments

• NVIDIA GPU with Compute Capability 8.6 or higher (e.g., NVIDIA Ampere-based GPUs like A100, RTX 30 series).

1. CUDA Toolkit:

   • Version 11.4 or higher.
   • Includes nvcc compiler and runtime libraries.
   • Download: CUDA Toolkit.

2. C++ Compiler:

   • g++ 9.4 (for Linux) or a compatible version.

3. Build Tools:

   • make utility is required to build the project.

Installation

This solver uses our GPU Linear Algebra Simple Subrotoutines (GLASS) library as a submodule, as it has proved to be faster for smaller problems than the traditional cuBLASS library.

Clone the repository and initialize the submodule, then run make command in the src folder.

git clone  --recurse-submodules https://github.com/A2R-Lab/BCHOL.git
cd BCHOL
cd src
make

Usage

After running the make command you should have the ./rsLQR executable in the src folder. Run it to see the example of the solver provided by Brian Jackson.

./rsLQR

You can run your example by putting the 'csv' file of the LQR problem in \exmpls folder and changing the name of the example in solve_lqe.cu line 53 :

read_csv("../exmpls/lqr_prob8.csv", knot_points, state_size, control_size, Q_R, q_r, A_B, d);

Documentation

It is highly recommended to read the paper A Parallell Linear System Solver for Optimal Control by Brian E. Jackson prior to using this code.

Additional documentation and graphical explanation has been provided by Yana Botvinnik here.