Metadata-Version: 2.2
Name: apxchol
Version: 0.2.0
Summary: CPU approximate-Cholesky preconditioner for graph-Laplacian / SDDM linear systems
Keywords: laplacian,preconditioner,cholesky,sparse,pcg
Author: Oleksandr Kulkov
License: Academic Evaluation License (interim)
         
         Copyright (c) 2026 ETH Zürich and the apxchol contributors.
         All rights reserved.
         
         This software is provided free of charge for academic research and
         evaluation purposes only. Redistribution, sublicensing, or commercial
         use, in source or binary form, is prohibited without prior written
         permission from the copyright holders.
         
         THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
         OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
         MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
         IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
         CLAIM, DAMAGES OR OTHER LIABILITY ARISING FROM THE USE OF THE SOFTWARE.
         
         This is an interim license intended to enable early access while a
         final license is selected; it may be replaced in a future release.
         
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: C++
Classifier: Intended Audience :: Science/Research
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: License :: Other/Proprietary License
Classifier: Operating System :: POSIX :: Linux
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Project-URL: Homepage, https://github.com/AlgOptGroup/apxchol
Project-URL: Repository, https://github.com/AlgOptGroup/apxchol
Project-URL: Issues, https://github.com/AlgOptGroup/apxchol/issues
Requires-Python: >=3.10
Requires-Dist: numpy>=1.21
Requires-Dist: scipy>=1.7
Provides-Extra: test
Requires-Dist: pytest>=7; extra == "test"
Description-Content-Type: text/markdown

# apxchol (Python, CPU)

Approximate-Cholesky preconditioner for graph-Laplacian / SDDM linear systems.

```bash
pip install apxchol
```

Prebuilt wheels: Linux x86_64 (manylinux), CPython 3.10–3.14. CPU only.
The wheels are built with 32-bit indices: inputs (and factors) beyond ~2.1e9
nonzeros are unsupported — build from source with
`-DAPXCHOL_64BIT_EDGE_INDICES=ON` for larger problems.

```python
import apxchol

solver = apxchol.factorize(A)           # scipy sparse Laplacian or SDDM; factor once
res = solver.solve(b, rtol=1e-8, maxiter=500)
res.x, res.iters, res.residual, res.converged

z = solver.apply(r)                     # M^{-1} r
M = solver.aspreconditioner()           # use as M= in scipy.sparse.linalg.cg

res = apxchol.solve(A, b)               # one-shot convenience
```

Laplacian vs SDDM is auto-detected: singular Laplacians get a rank-(n−1)
factor with native null-space handling; SDDM systems get the full-rank factor.
The factor is built once per `factorize(A)` (alias: `apxchol.solver(A)`) and
reused across right-hand sides; `solve` runs the library's OpenMP-parallel PCG
(threads via `OMP_NUM_THREADS`).

## Solving

```python
res = solver.solve(b, rtol=1e-8, maxiter=500, x0=guess)
```

`rtol` is the relative-residual target (SciPy's name; `tol` is kept as an
alias and `rtol` wins if both are given, default `1e-8`). `x0` is an optional
initial guess — an already-converged `x0` returns `iters == 0`.

`out` is an optional writable C-contiguous float64 array of length `n`: the
solution is written into it in place (no per-solve allocation) and returned as
`SolveResult.x`.

## Options

```python
solver = apxchol.factorize(A, seed=42, partitioner="block_greedy",
                           storage="vec_pool", keep_factor=True)
```

- `seed` — RNG seed for the randomized clique sampling.
- `partitioner` — independent-set selector: `block_greedy` (default), `luby`,
  `baumann_kyng`, `rootset`.
- `storage` — graph backend: `vec_pool` (default), `forward_star`, `vec`, `bstr`.
- `keep_factor` — keep the factor arrays alive for export (default `True`).
  Costs one extra factor-sized copy in memory (~8 bytes per factor nonzero in
  the default fp32 wheels); with `keep_factor=False` the `chol()`/`L`/`D`
  export raises, while `P`, `factor_nnz` and `fill_ratio` stay available.
  Pass `keep_factor=False` for the leanest factor-once / solve-many footprint
  (the 0.1.x behavior); `apxchol.solve()` (one-shot) uses `False`.

Advanced core knobs are passed through as extra keywords:
`degree_quantile`, `degree_multiplier`, `degree_tiebreak`,
`exact_clique_max_degree`, `residual_peel`
(`natural` | `min_degree` | `bk_serial`), `stagnation_window`. Unknown
keywords raise `ValueError`. Note: `degree_multiplier` only takes effect when
`degree_quantile=0` (the quantile cap, default 0.2, replaces it).

## Factor export

```python
P = solver.P            # int64: P[original_vertex] = position in elimination order
G = solver.chol()       # scipy.sparse.csc_matrix, lower-triangular incl. sqrt-diagonal
L, D = solver.L, solver.D          # unit-lower CSC and the diagonal of L·D·L^T
solver.factor_nnz, solver.fill_ratio
```

The factor lives in **permuted** space, ordered by elimination:

```python
import numpy as np
import scipy.sparse as sp

p = np.argsort(solver.P)     # original index of the k-th eliminated vertex
A_perm = A[p][:, p]
# A_perm ~= G @ G.T ~= L @ sp.diags(D) @ L.T
```

`G` is an *approximate*, randomly sampled factor, so that identity is
approximate by construction; `L @ diags(D) @ L.T == G @ G.T` is exact. For a
pure Laplacian (`solver.sddm == False`) it holds on the rank-(n−k) subspace
only, where k is the number of connected components — the last eliminated
column of each component carries a placeholder diagonal.

`fill_ratio` is `(2 * factor_nnz - n) / nnz(A)`: the factor `G` reflected to a
full symmetric pattern (diagonal counted once) against the nonzeros of the full
symmetric `A`.

Exported values are float64 numpy arrays, but default builds store factor
values in fp32, so they carry fp32 precision (~7 digits).

## Thread safety

A `Solver` is not safe for concurrent use: `solve()` and `apply()` write shared
internal scratch buffers. Use one `Solver` per thread, or serialize calls
(each call is itself OpenMP-parallel).

## License

Interim academic-evaluation license: free for academic research and
evaluation; redistribution and commercial use prohibited. See `LICENSE`.

## From source

The wheel build compiles the library's two core translation units directly;
building from a repository checkout works the same way:

```bash
pip install -e python          # from the repository root
pytest python/tests -v
```

Source builds use `-O3 -march=native` (the distributed wheels are built
portable). If your environment requires `--no-build-isolation`, first
`pip install pybind11 scikit-build-core`.
