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

Until the next release, pip installs 0.2.2, which solves one right-hand side per call and has no as_operator. To run this example, install the development version from source.

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

Wheels run on CPU without a GPU and include CUDA (Linux) or Metal (macOS). See installation for the latest release, CLI archives and source builds.

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.as_operator(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. solver.apply (C++) and aslinearoperator() (Python) let you use the preconditioner with another iterative solver. See integration and factor reuse.

Build and run

Standalone CLI archives for Linux CPU and Apple-silicon CPU/Metal need no Python.

A source build needs CMake 3.20+ and GCC or Clang with C++23 and OpenMP. See building from source 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 reads the matrix as A. --convert-input forms the Laplacian of an adjacency matrix. An --rhs file with several columns is solved as one batch. --random-rhs generates a test RHS. The command-line guide lists the available controls.

Performance

Cross-solver results will appear in 1.0. See performance for the methodology and the measured batching case study.

Learn more

• Installation and building from source
• Choosing a backend, reusing factors and checking results
• Precision and API compatibility
• Examples, custom algorithms 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 · Citing apxchol · Changelog.

Acknowledgements

Samuel Talkington contributed the Apple Metal backend and macOS support.