RandLAPACK

RandLAPACK is a C++ library of high-performance randomized algorithms for linear algebra problems such as least squares, (kernel) ridge regression, low-rank approximation, and matrix factorizations. Its API is not yet stable; we are actively working on changing that.

RandLAPACK builds on RandBLAS, a header-only C++ library for sketching in randomized linear algebra (sketching compresses a matrix by multiplying it with a random one). RandBLAS comes with RandLAPACK as a pinned git submodule (another git repository included at one fixed commit), so you do not install it separately. randlapack-bindings provides MATLAB bindings (Python is planned): currently a proof of concept for BQRRP (blocked QR with randomized column pivoting), in single and double precision.

Questions, or want to get involved in development? Join our Discord server.

What's in the library

The user-facing algorithms, called "drivers" (docs/ARCHITECTURE.md explains how the library is organized):

Driver	Problem it solves	Reference
BQRRP	Blocked QR with randomized column pivoting, any aspect ratio	arXiv:2507.00976
CQRRPT	Sketch-based QR with column pivoting for tall matrices	arXiv:2311.08316
CQRRT	Unpivoted QR of tall, full-rank matrices by sketch-preconditioned Cholesky QR; CQRRTO_linops is its Q-less variant for linear operators	arXiv:2111.11148
Blendenpik_linops	Tall least squares by sketch-and-precondition: LSQR preconditioned with the QR of a sparse sketch	doi:10.1137/090767911
RSVD	Randomized low-rank SVD via the QB decomposition, of a dense matrix or any linear operator (sparse or implicit)	arXiv:0909.4061
REVD2	Randomized low-rank eigendecomposition of symmetric positive semidefinite matrices	arXiv:2110.02820
ABRIK	Block-Krylov iterative SVD for many accurate singular triplets	arXiv:2306.12418
hqrrp	Householder QR with randomized pivoting	arXiv:1512.02671
krill_full_rpchol	Kernel ridge regression by conjugate gradients, preconditioned with randomly pivoted Cholesky	arXiv:2304.12465

• BQRRP and CQRRPT also have CUDA (GPU) implementations, BQRRP_GPU and CQRRPT_GPU.
• CholQR_linops, CholQR2_linops, sCholQR3_linops and sCholQR3_linops_basic are deterministic Cholesky QR baselines for linear operators, for comparison with CQRRTO_linops.
• IterRefineLSQ solves tall least-squares problems by restarted conjugate gradients on the normal equations, preconditioned with the triangular factor of a Q-less QR such as CQRRTO_linops. It and Blendenpik are built on two routines you can also call directly: lsqr (LSQR with an optional triangular right preconditioner) and restarted_pcg_ne.
• The drivers are assembled from smaller randomized building blocks that you can also use on their own: rangefinders, QB, block Krylov, row sketching, orthogonalization and stabilization routines, and randomly pivoted Cholesky (rp_cholesky).
• The RandNLA monograph (arXiv:2302.11474) is the best background reference for these algorithm families.

Install

Linux and macOS

First install a C++20 compiler (GCC 13 or newer on Linux), CMake 3.24 or later, Git, a BLAS/LAPACK library (the standard low-level linear algebra routines) and GoogleTest. These are the packages CI installs:

# Ubuntu 24.04
sudo apt-get update && sudo apt-get install git-core gcc g++ gfortran cmake libgtest-dev libopenblas-openmp-dev

# macOS: the built-in Accelerate provides BLAS/LAPACK; libomp adds multithreading
xcode-select --install
brew install cmake googletest libomp

Without GoogleTest, no tests are built. To use Intel oneMKL instead of OpenBLAS, load oneAPI's environment (source <oneapi>/setvars.sh) first. On a machine with an NVIDIA GPU, read the GPU note in INSTALL_SCRIPT.md, section 2. Then build and install:

git clone --recursive https://github.com/BallisticLA/RandLAPACK.git
cd RandLAPACK
bash install.sh

Check the install by running the test suite. The installer's final summary prints this build directory; it differs if you set RANDNLA_PROJECT_DIR.

OMP_NUM_THREADS=1 ctest --test-dir ../RandNLA-project/build/RandLAPACK-build -j 4

The installer builds RandLAPACK, its dependencies, the extras and benchmark projects, and the test suite. The dependencies are BLAS++ and LAPACK++ (C++ wrappers for BLAS and LAPACK, built from the BallisticLA forks), Random123, and RandBLAS, from its submodule. Run bash install.sh --help for the options: GPU support, parallelism, reusing preinstalled dependencies, and more.

Native Windows

From an "x64 Native Tools Command Prompt for VS 2022" (INSTALL_WINDOWS.md explains which prompt to open, and why):

mkdir C:\src & cd /d C:\src
git clone --recursive https://github.com/BallisticLA/RandLAPACK.git
cd RandLAPACK
powershell -ExecutionPolicy Bypass -File .\installers\install.ps1

This builds the dependencies and RandLAPACK and runs the test suite; it does not build the extras or benchmark projects.

From your own project, and by hand

• To use RandLAPACK from your own CMake project, with a minimal example program, see docs/USING.md.
• To build every piece by hand instead, see docs/INSTALL_MANUAL.md. This is an advanced, riskier option: the installers keep the dependencies consistent for you.

docs/DEPENDENCIES.md lists the hardware and software setups where RandLAPACK has been tested.

Where to go from here

You want to...	Read
Install with one command on Linux or macOS	docs/INSTALL_SCRIPT.md
Install on native Windows (MSVC)	docs/INSTALL_WINDOWS.md
Use RandLAPACK from your own CMake project (with an example program)	docs/USING.md
Install by hand (advanced, riskier)	docs/INSTALL_MANUAL.md
See the tested setups, dependency versions and CUDA requirements	docs/DEPENDENCIES.md
Understand how the library is organized	docs/ARCHITECTURE.md
Contribute code	CONTRIBUTING.md
See what CI checks, and why	docs/CI.md
Run or add performance benchmarks	benchmark/README.md
Use the Eigen/Matrix-Market integrations	extras/README.md