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.5.0.tar.gz (108.2 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.5.0-cp314-cp314t-win_amd64.whl (214.9 kB view details)

Uploaded CPython 3.14tWindows x86-64

approx_chol-0.5.0-cp314-cp314t-manylinux_2_34_x86_64.whl (334.3 kB view details)

Uploaded CPython 3.14tmanylinux: glibc 2.34+ x86-64

approx_chol-0.5.0-cp314-cp314t-macosx_11_0_arm64.whl (304.4 kB view details)

Uploaded CPython 3.14tmacOS 11.0+ ARM64

approx_chol-0.5.0-cp39-abi3-win_arm64.whl (213.9 kB view details)

Uploaded CPython 3.9+Windows ARM64

approx_chol-0.5.0-cp39-abi3-win_amd64.whl (225.0 kB view details)

Uploaded CPython 3.9+Windows x86-64

approx_chol-0.5.0-cp39-abi3-win32.whl (209.2 kB view details)

Uploaded CPython 3.9+Windows x86

approx_chol-0.5.0-cp39-abi3-musllinux_1_2_x86_64.whl (555.0 kB view details)

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

approx_chol-0.5.0-cp39-abi3-musllinux_1_2_i686.whl (581.5 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ i686

approx_chol-0.5.0-cp39-abi3-musllinux_1_2_armv7l.whl (624.5 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ ARMv7l

approx_chol-0.5.0-cp39-abi3-musllinux_1_2_aarch64.whl (515.1 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ ARM64

approx_chol-0.5.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (342.4 kB view details)

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

approx_chol-0.5.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl (375.0 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ s390x

approx_chol-0.5.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (381.8 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ppc64le

approx_chol-0.5.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (349.7 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ARMv7l

approx_chol-0.5.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (338.2 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ARM64

approx_chol-0.5.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl (363.5 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.5+ i686

approx_chol-0.5.0-cp39-abi3-macosx_11_0_arm64.whl (314.3 kB view details)

Uploaded CPython 3.9+macOS 11.0+ ARM64

approx_chol-0.5.0-cp39-abi3-macosx_10_12_x86_64.whl (321.5 kB view details)

Uploaded CPython 3.9+macOS 10.12+ x86-64

File details

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

File metadata

  • Download URL: approx_chol-0.5.0.tar.gz
  • Upload date:
  • Size: 108.2 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.5.0.tar.gz
Algorithm Hash digest
SHA256 72980a18428464f3d7076b8a7c4560b478f93752c6a2f02fdf7a6057d3e71e51
MD5 520c393248591fc9c8b557ef56888b20
BLAKE2b-256 f045d135d2b2dce5374e4339775f8e3e0e7de92c04e96396de5e23697913f3a9

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp314-cp314t-win_amd64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp314-cp314t-win_amd64.whl
Algorithm Hash digest
SHA256 f098003c989c1a61b3ebb7adb0a95a161c97573be331e301b751f44f5a1f02a8
MD5 1445b1ed39c7c40a782c73b56608d5c3
BLAKE2b-256 e0f68cde96b960d66d3075057340677f6b4236dba49e1af2db50a3976b78324d

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp314-cp314t-manylinux_2_34_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp314-cp314t-manylinux_2_34_x86_64.whl
Algorithm Hash digest
SHA256 7d3d6fc504f6e4cf6b657fc7d0fab7c168a68daeec1dfeb13cdbc169ef909ac4
MD5 44e0db97eb877c40a297acdf1b95e59c
BLAKE2b-256 7a70eba1a93fd13501ba556eca0064bb48cd598b3f78e6e910967e2871f35586

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp314-cp314t-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp314-cp314t-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 313b2df70f34306bd4a7226bf0a88389bacdc69ae3a1e99822cac6540cb7ef71
MD5 3e78714c95630d8dae7dfab672d3f862
BLAKE2b-256 d815e8f12dfda6fb675a608c8a8df1436892626dbaec42f443cea5155564fd22

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-win_arm64.whl.

File metadata

  • Download URL: approx_chol-0.5.0-cp39-abi3-win_arm64.whl
  • Upload date:
  • Size: 213.9 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.5.0-cp39-abi3-win_arm64.whl
Algorithm Hash digest
SHA256 e575219a1191dd8fa9bbfde67eb8757c117e36041cf0723385ae45b76d53ebb0
MD5 cc1503e656b58b9baf520e53254cf45e
BLAKE2b-256 7d46ff431f6c2864a03bf198a4690ca116a1261080fc50c5da485822b23d5782

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-win_amd64.whl.

File metadata

  • Download URL: approx_chol-0.5.0-cp39-abi3-win_amd64.whl
  • Upload date:
  • Size: 225.0 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.5.0-cp39-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 2333dff7632f91404dcd57aa948c00dff8bc7998fc50610aa323e0f5b9a07a51
MD5 1290434ea79fbe61a63e1bead6e871a7
BLAKE2b-256 75dacdbd7d97d43ba2bb02ed64eb61cb476b8ae68b2896cbc00dad72c4337b41

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-win32.whl.

File metadata

  • Download URL: approx_chol-0.5.0-cp39-abi3-win32.whl
  • Upload date:
  • Size: 209.2 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.5.0-cp39-abi3-win32.whl
Algorithm Hash digest
SHA256 709dba6c30ba04249e55275aba640e1b6ad445438064925534adce0a02587f76
MD5 2e4563d3c5820c9626ad53580c89a3d0
BLAKE2b-256 6ea903a4e671d30b018be19ea0f87d14c28915df95d6c2ac2be4a9099fb5ec22

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 db41fd21b779e7624289697d5cead67d0422e4d1d1d019599b48b5a7da6d1598
MD5 eef97bf4c3d34ed99725308ebb511394
BLAKE2b-256 36d0ded481db4c1493e6dc12d297a8836ea1ac9278516f2a2631721543895cbe

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-musllinux_1_2_i686.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-musllinux_1_2_i686.whl
Algorithm Hash digest
SHA256 7ea2c323cc1172ae3b0fa4829446f7c8d9b149f9786377c8fe2325d02a645d2b
MD5 7ba4bbc6d5d3499df4bead4fe6911631
BLAKE2b-256 0089b571c871bb2a2a99409d4e3dad733a31c1877b18e4cab83cbe3433b48c1b

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-musllinux_1_2_armv7l.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-musllinux_1_2_armv7l.whl
Algorithm Hash digest
SHA256 1fc0a77af68a61ffdf11b36e3ceab53dc2c6b2edc2b72675091b606b2ad6569f
MD5 c7c9a0117ed26571d796c68734975040
BLAKE2b-256 8eb17c777664fbd02eb0ff8340b6741e7888ce5d54439c54bc8072e4c940349b

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-musllinux_1_2_aarch64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-musllinux_1_2_aarch64.whl
Algorithm Hash digest
SHA256 3b04b7ec4024f936eb26122bb702f3e2718ee36bce62dc1787b28bbc296f197f
MD5 ec31027a2b4a05bfac52979b06ba2949
BLAKE2b-256 6edb77a9ba702b80565e1e1d05f611df9aa137ddbd201316bc2d14e19a237e8e

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 f2cec4625069a1f0bb334ab464cbf79a691fa4eda5b238464f5894bb0f7e817e
MD5 a0bb6035c74c12cb99b2af4b93053b6d
BLAKE2b-256 165187c7d76ca6cc9f7c13fc2e27ab178676602db8def5334b3ce5e469bf5999

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
Algorithm Hash digest
SHA256 8a4838e6c7c1450d1c78df1897dd8fb7d1c100cced5e1e7ad3f4a7f0f9cb56eb
MD5 1b29b1732aa9cae1276b0d7c107e9d51
BLAKE2b-256 ef2b5da5d5e8920ecee83ac2319920c4292fbe32f88f2290c70ec73f2db67025

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
Algorithm Hash digest
SHA256 ed2ed618b491745749c2b7d651e2b9694f3863676b0da167662737a10c835c54
MD5 61f41106d88dc60af102599ca31974d4
BLAKE2b-256 32e4a1cb21aebd539f5c0f2b2e96b8417ade9e613563f84c26ead1839ba2c53b

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
Algorithm Hash digest
SHA256 acdc1f9e9981103b42ebe736092f4ea9c562b57a348256854dbab55c0684109c
MD5 aacf03117ccbce4eacb7ba8aa6e5937a
BLAKE2b-256 a8caa2b1fd59f750968791f1db10741137f47c49298fb55f4337b153cde530ec

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 ccb0251dd2fa9bc2f6ed693ca981891c51ad0f092606458ad20507d4a741483f
MD5 2a6fe5e126f191ce4bf039a5c3ec7110
BLAKE2b-256 5c05892241d56fe48e701a6c017f890466ff5222692feb572334e6f30682a41f

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl
Algorithm Hash digest
SHA256 fa6504e147ffbd0407c8e1671958184f85d75ddde35d1bc38c1c942e7f77841b
MD5 41ba48569c282d68dd94aae7ae02eff6
BLAKE2b-256 70f45223d0f97916bdb2d5107f89116fbc023e70c9534cccd5d57aeef506d0c3

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 f673fbced3ea4282c4c37bc62c057ea6f9998297199bb551582ea9ad915c55d9
MD5 f2f3b3e98570f4d2bc15a6f1ea9fbdef
BLAKE2b-256 697c6086863cc199fc14f1d06aa368cba50f5009ed9aca36ca49e777fa771546

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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.5.0-cp39-abi3-macosx_10_12_x86_64.whl.

File metadata

File hashes

Hashes for approx_chol-0.5.0-cp39-abi3-macosx_10_12_x86_64.whl
Algorithm Hash digest
SHA256 715b35dbaafe3068eeb3e2ffa2f2c33293387698fa485992405c428e50bc9896
MD5 a7ac25270ac687de681ee6c8a5c80cd9
BLAKE2b-256 5abaa8d0642a5fa25bb361ba169d4da3e35e96aa398a08b714fa7a6e3672a9d6

See more details on using hashes here.

Provenance

The following attestation bundles were made for approx_chol-0.5.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