apxchol

apxchol solves sparse graph-Laplacian and SDDM linear systems, A x = b. It builds an approximate-Cholesky preconditioner and uses preconditioned conjugate gradients (PCG) to compute the solution.

• Reuse one factorization for single or batched right-hand sides.

• Run on multicore CPUs, NVIDIA GPUs or Apple GPUs.

• Get convergence results verified against your original matrix and RHS.

Quick start

For an unreleased checkout, use a source installation with the scipy extra. For the latest published package, see PyPI for that version’s API and install with:

python -m pip install "apxchol[scipy]"

import apxchol
import numpy as np
from scipy.sparse import diags

n = 1000
# Tridiagonal matrix: 3 on the diagonal, -1 directly above and below it.
A = diags([-1.0, 3.0, -1.0], [-1, 0, 1], shape=(n, n), format="csc")
solver = apxchol.factorize(A)
result = solver.solve(np.ones(n), rtol=1e-8)
assert result.converged

# Solve several RHS columns together, reusing the same factorization.
B = np.column_stack((np.ones(n), np.arange(n)))
batch = solver.solve(B)
assert batch.converged.all()           # solutions are in batch.x

No GPU is required. Wheels built by this project include the CPU solver plus CUDA on Linux or Metal on macOS. GPU execution needs a compatible device and driver, but using the wheels requires neither the CUDA Toolkit nor Homebrew.

Wheel builds	Minimum platform	Included backends
CPython 3.11–3.15 / PyPy 7.3.23, Linux	x86-64-v2 CPU, glibc 2.28	CPU + CUDA
CPython 3.11–3.15 / PyPy 7.3.23, macOS	macOS 15, Apple silicon	CPU + Metal

PyPy wheels use Python 3.11 (pp73). On PyPy, use the NumPy-only interface.

solver.backend reports which backend was selected. Use backend="cpu" or backend="gpu" in factorize to choose explicitly.

Pass the matrix A from A x = b. For a graph adjacency matrix, first form its Laplacian with apxchol.laplacian(Adj). See the solver guide for supported matrices and convergence checks.

Interfaces

Start with the built-in solver for factor reuse and batched solves. The Python, C++ and MATLAB/Octave guides cover each interface. Eigen and SciPy adapters let you use the preconditioner with another iterative solver; see integration and factor reuse.

Build and run

Standalone CLI archives are built by CI for Linux CPU and Apple-silicon CPU/Metal; new releases attach these downloads. Python is not required.

A source build needs CMake, GCC or Clang with C++23 and OpenMP, and Eigen. See building and installation for dependencies, GPU builds and CMake integration.

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j6
ctest --test-dir build --output-on-failure
./build/apxchol matrix.mtx --rhs rhs.mtx -o solution.mtx

The CLI also accepts adjacency matrices. --random-rhs generates a test RHS; --help lists the available controls.

Performance

See performance results and methodology and batching and factor reuse for measured examples and guidance.

Learn more

• Building and installation

• Choosing a backend, reusing factors and checking results

• Precision and API compatibility

• Custom algorithms, examples and contributing

• Benchmarking and reproducibility

Based on Kyng–Sachdeva (2016), Gao–Kyng–Spielman (2023) and Baumann–Kyng (2024).

Developed at ETH Zürich. Contact: apxchol@inf.ethz.ch. License · Citation.