Skip to main content

approx-chol

Approximate Cholesky factorization for SDDM and graph Laplacian systems.

This package implements AC and AC(k), porting key algorithmic ideas from Laplacians.jl to make these algorithms accessible in Python.

AC(k) was introduced and analyzed by Gao, Kyng, and Spielman (2025), "AC(k): Robust Solution of Laplacian Equations by Randomized Approximate Cholesky Factorization" (SIAM Journal on Scientific Computing, November 2025, ISSN 1064-8275).

Install

pip install approx-chol

Usage

import numpy as np
from scipy.sparse import csr_array
from approx_chol import factorize

# 4-node path graph Laplacian (0-1-2-3)
row_ptrs = np.array([0, 2, 5, 8, 10], dtype=np.uint32)
col_indices = np.array([0, 1, 0, 1, 2, 1, 2, 3, 2, 3], dtype=np.uint32)
values = np.array([1.0, -1.0, -1.0, 2.0, -1.0, -1.0, 2.0, -1.0, -1.0, 1.0])

laplacian = csr_array((values, col_indices, row_ptrs), shape=(4, 4))

factor = factorize(laplacian)

# RHS must lie in the range of the Laplacian (sum to zero)
b = np.array([1.0, -1.0, 1.0, -1.0])
x = factor.solve(b)

Configuration

from approx_chol import Config, factorize

config = Config(seed=42, split=3)
factor = factorize(laplacian, config=config)

Low-level API

For direct control over CSR arrays without constructing a scipy sparse matrix:

from approx_chol import factorize_raw

factor = factorize_raw(row_ptrs, col_indices, values, n=4)
x = factor.solve(b)

API

  • factorize(matrix, config=None) — Factorize a scipy.sparse.csr_array or csr_matrix.
  • factorize_raw(row_ptrs, col_indices, values, n, config=None) — Factorize from raw CSR arrays.
  • Factor.solve(b) — Solve LDL^T x = b, returning a new array.
  • Factor.solve_into(b, out) — Solve in-place into a pre-allocated array.
  • Config(seed=0, split=None, backend=None) — Configuration for the factorization.
  • Backend.Approximate() / Backend.ExactBelow(max_dim, on_failure) — Which factorization each block gets; defaults to ExactBelow(24, ExactFailure.FallBackToApproximate).
  • Factor.fallbacks — Blocks routed to exact Cholesky and factored approximately anyway; also raises a RuntimeWarning.

Attribution

This package ports key algorithmic ideas from Laplacians.jl to make AC and AC(k) accessible in Python.

Laplacians.jl is licensed under the MIT License.

License

MIT — see LICENSE.

References

  • Gao, Yuan; Kyng, Rasmus; Spielman, Daniel (2025). AC(k): Robust Solution of Laplacian Equations by Randomized Approximate Cholesky Factorization. SIAM Journal on Scientific Computing.
  • Gao, Kyng & Spielman (2023). Robust and Practical Solution of Laplacian Equations by Approximate Elimination. https://arxiv.org/abs/2303.00709
  • Kyng & Sachdeva (2016). Approximate Gaussian Elimination for Laplacians — Fast, Sparse, and Simple. https://arxiv.org/abs/1605.02353

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

approx_chol-0.4.0.tar.gz (96.6 kB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

approx_chol-0.4.0-cp314-cp314t-win_amd64.whl (231.3 kB view details)

Uploaded CPython 3.14tWindows x86-64

approx_chol-0.4.0-cp314-cp314t-manylinux_2_34_x86_64.whl (344.5 kB view details)

Uploaded CPython 3.14tmanylinux: glibc 2.34+ x86-64

approx_chol-0.4.0-cp314-cp314t-macosx_11_0_arm64.whl (315.4 kB view details)

Uploaded CPython 3.14tmacOS 11.0+ ARM64

approx_chol-0.4.0-cp39-abi3-win_arm64.whl (218.1 kB view details)

Uploaded CPython 3.9+Windows ARM64

approx_chol-0.4.0-cp39-abi3-win_amd64.whl (232.3 kB view details)

Uploaded CPython 3.9+Windows x86-64

approx_chol-0.4.0-cp39-abi3-win32.whl (218.9 kB view details)

Uploaded CPython 3.9+Windows x86

approx_chol-0.4.0-cp39-abi3-musllinux_1_2_x86_64.whl (559.4 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ x86-64

approx_chol-0.4.0-cp39-abi3-musllinux_1_2_i686.whl (587.5 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ i686

approx_chol-0.4.0-cp39-abi3-musllinux_1_2_armv7l.whl (635.0 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ ARMv7l

approx_chol-0.4.0-cp39-abi3-musllinux_1_2_aarch64.whl (518.5 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ ARM64

approx_chol-0.4.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (347.9 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ x86-64

approx_chol-0.4.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl (383.5 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ s390x

approx_chol-0.4.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (388.1 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ppc64le

approx_chol-0.4.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (359.0 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ARMv7l

approx_chol-0.4.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (342.7 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ARM64

approx_chol-0.4.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl (370.4 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.5+ i686

approx_chol-0.4.0-cp39-abi3-macosx_11_0_arm64.whl (318.8 kB view details)

Uploaded CPython 3.9+macOS 11.0+ ARM64

approx_chol-0.4.0-cp39-abi3-macosx_10_12_x86_64.whl (335.3 kB view details)

Uploaded CPython 3.9+macOS 10.12+ x86-64

File details

Details for the file approx_chol-0.4.0.tar.gz.

File metadata

  • Download URL: approx_chol-0.4.0.tar.gz
  • Upload date:
  • Size: 96.6 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for approx_chol-0.4.0.tar.gz
Algorithm Hash digest
SHA256 076b42925f18db543d77aaab5aad9d2a9fc629dde2caba4f8ad8c20f4a32e582
MD5 01ae9c96c6ff1126185c0a9f9fde0ab2
BLAKE2b-256 1ef97139fe12c4e74d392075629adc599e10af58e1a5ade50d895be036c28f0b

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0.tar.gz:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp314-cp314t-win_amd64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp314-cp314t-win_amd64.whl
Algorithm Hash digest
SHA256 f0c14ae25120171077eef276d3773710a8ca3c1a65d9271c6e0426890537fe3a
MD5 2f8d070004a3dc8ce91b1f934b3424e5
BLAKE2b-256 e75926b1f6966c5a24501add60765bcfa9e061f8f1982c7d2279df0faf401871

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp314-cp314t-win_amd64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp314-cp314t-manylinux_2_34_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp314-cp314t-manylinux_2_34_x86_64.whl
Algorithm Hash digest
SHA256 bb2ed21ca7983966c27bf913565d34281c9e93a66b3b15927d99fa8bb72f8436
MD5 62fa463ced352ec46a6b43f91969e02e
BLAKE2b-256 103d85f1ee07b4bd40c0c77917d2f2afe36e35e5cd1e6914ff8794a9a9fedb75

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp314-cp314t-manylinux_2_34_x86_64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp314-cp314t-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp314-cp314t-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 c787af46d1b3fefdb0e98833ba57677718edab335ae876953e0cc16e158916ae
MD5 5cb10ebd87c58eaa183e57f10bd762f8
BLAKE2b-256 6122bc4bd99e2865c9fee26f11f433003dfd19520baa129e586555dc9bc57a2d

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp314-cp314t-macosx_11_0_arm64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-win_arm64.whl.

File metadata

  • Download URL: approx_chol-0.4.0-cp39-abi3-win_arm64.whl
  • Upload date:
  • Size: 218.1 kB
  • Tags: CPython 3.9+, Windows ARM64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-win_arm64.whl
Algorithm Hash digest
SHA256 4e4270ca8c5cdb036eff7a2c63ae4907e173c9949c848083972eab0dadeca05d
MD5 a6a0eae1b0c288592abf7572b1082a65
BLAKE2b-256 4bd27833efc6c4aacdb2a794c16e060a36f5d939bf6ac015161ed33d5abb23ce

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-win_arm64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-win_amd64.whl.

File metadata

  • Download URL: approx_chol-0.4.0-cp39-abi3-win_amd64.whl
  • Upload date:
  • Size: 232.3 kB
  • Tags: CPython 3.9+, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 0d866a5212590adbb8de0382f4c66c14c30b6ae2ac9822262775cd03b0fd58b1
MD5 a36da16986f2bd00f2ea2e4008f0b27c
BLAKE2b-256 18530976f31365cfa4e741fa08666e3605c4b7cc3018ed1a4143d3b5364c5a1e

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-win_amd64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-win32.whl.

File metadata

  • Download URL: approx_chol-0.4.0-cp39-abi3-win32.whl
  • Upload date:
  • Size: 218.9 kB
  • Tags: CPython 3.9+, Windows x86
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-win32.whl
Algorithm Hash digest
SHA256 a4e73a353f37543aedb0a418a610102c3e9cbd339f683fe3657844aebed4d035
MD5 417b82b6cf54ae00f9e511733c6b0a8c
BLAKE2b-256 79d6fbdc73c518d1cdcd92d70c479f95d762a1a1922ef75b4f1e7bd343ccd8fb

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-win32.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 3fdbb748bbe3e4f7b99b70a0dcf36efadb959f06d60f3d02d134d28f4738b9fe
MD5 e3d399a87b1dffee149e81a09b0a89f4
BLAKE2b-256 84e878a4482cd5db9e95ba3d1669c7df5cd61c780148b9d4d7e261940e33f6a9

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_x86_64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-musllinux_1_2_i686.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_i686.whl
Algorithm Hash digest
SHA256 809c931e54fb2d4e27da426c0b79218426fc68543ca2ee50a14c3768e9c97ed0
MD5 8a8da2e47c119e43c7020d0db623fad4
BLAKE2b-256 2b80652b17d72761c6bec41f5867d8e7233d8796da14220a616d1159068a77c9

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_i686.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-musllinux_1_2_armv7l.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_armv7l.whl
Algorithm Hash digest
SHA256 6189cf1173255b0f7de8de1d41477a762bfca077bffc4a38997b29141df272ff
MD5 f7f1a555e85280386a40ddf799ebfd79
BLAKE2b-256 578b37916cea955d0e9652fa50292160e0140142d8ecf92d1c7dbf83f33050bb

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_armv7l.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-musllinux_1_2_aarch64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_aarch64.whl
Algorithm Hash digest
SHA256 28323fea6f8be5b705cb8a64d7e9a342506be5c523b6faeef77120122f82dff6
MD5 170b84ea5374e4470d5e57fb0de613a4
BLAKE2b-256 66843cbbb4aa07764834d8cf437460191d2a172fced47c327cbfc586670411ac

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-musllinux_1_2_aarch64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 94b021842f9fe8011eaf049d6b96debff7a68d56b90713ccfd3d2d4fef66a03e
MD5 3fedc46a4dc21cb8164bf62172f668ba
BLAKE2b-256 b4e66aeef99de03fcf97230f54bfa112340545c0c80eec506f916bd81509bc99

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
Algorithm Hash digest
SHA256 d78237217a18baf0f14b3793ccb4e5e5ac8c80ec7331d97747893912bf7865c6
MD5 fca418d14fd18b7839e3566a433d052b
BLAKE2b-256 e2c102c80fa90c59ee4e87255a751aee9e9758fe913dc6f408cf4ed2c01c1a2f

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
Algorithm Hash digest
SHA256 3c345b9ccaae19cdede1a3bad78cd939b3195a0cb7160304e7b7b312a59e273b
MD5 08d1d3aa981b3fa8fc4b4edb67b5b21d
BLAKE2b-256 0fef7890acfd0ff8fafedb53427e69028d099c37bc90ce9d76adf1b5bf19bad2

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
Algorithm Hash digest
SHA256 426052350043766fa2b7a888c66dad9795150cb83354b361d31cb1e591ca660f
MD5 8eb6fceb8fe954d8de2688113be4a8c9
BLAKE2b-256 289d87069606fd3b4dc7dc7a3a742772ca8ca2056c25269fd6ae077d464650f9

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 45278647ac2147dd520628130e654dbc5e32d42b0d71a4d9211224f71d1ad0d8
MD5 90985d073c86df976b2d0309d5ad469f
BLAKE2b-256 843cada2afe909f68563274b0c26fd811dbee18f332443eda431f764801b7a76

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl
Algorithm Hash digest
SHA256 3968ad3bbdb6b53dcf30f2da9f63e1cd101f2c766df047b7d22961c3607c0249
MD5 da55240e68bdb105fa41dc12d77ac0a6
BLAKE2b-256 ec1d789f6fb2374307be70075fed2fb892de2f22d553d95f7f50f521484cf9da

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 ece18795037c1b0c79a83e99da64fb9a86cbcbe3bc86850770eefe217b0db68a
MD5 1577136f83ff491a56e4ef42a53ca0b3
BLAKE2b-256 fe368db0eeb1b7c1c39026068c29507a6acf4c4ae8d370df13eea8d7bf43ca2b

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-macosx_11_0_arm64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file approx_chol-0.4.0-cp39-abi3-macosx_10_12_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.4.0-cp39-abi3-macosx_10_12_x86_64.whl
Algorithm Hash digest
SHA256 a00525cf039770425cd10854765cd11b0fd7d2870efd43c099ffd31016ebbd9c
MD5 611a878a156c47c0618b0973f27bc0e4
BLAKE2b-256 e9ffbd69b847d4dfd6743533f9fb95685c8cd8c4c53f84e849f0e74858b5659c

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.4.0-cp39-abi3-macosx_10_12_x86_64.whl:

Publisher: publish.yml on aai-institute/approx-chol

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Depot Continuous Integration Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page