Metadata-Version: 2.2
Name: apxchol
Version: 0.2.1
Summary: CPU approximate-Cholesky preconditioner for graph-Laplacian / SDDM linear systems
Keywords: laplacian,preconditioner,cholesky,sparse,pcg
Author: Oleksandr Kulkov
License: BSD 4-Clause License
         
         Copyright (c) 2026 ETH Zürich and the apxchol contributors.
         All rights reserved.
         
         Redistribution and use in source and binary forms, with or without
         modification, are permitted provided that the following conditions are met:
         
         1. Redistributions of source code must retain the above copyright notice,
            this list of conditions and the following disclaimer.
         
         2. Redistributions in binary form must reproduce the above copyright notice,
            this list of conditions and the following disclaimer in the documentation
            and/or other materials provided with the distribution.
         
         3. All advertising materials mentioning features or use of this software must
            display the following acknowledgement:
              This product includes software developed by ETH Zürich and the apxchol
              contributors.
         
         4. Neither the name of the copyright holder nor the names of its contributors
            may be used to endorse or promote products derived from this software
            without specific prior written permission.
         
         THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
         AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
         IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
         ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
         LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
         CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
         SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
         INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
         CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
         ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
         POSSIBILITY OF SUCH DAMAGE.
         
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: C++
Classifier: Intended Audience :: Science/Research
Classifier: Topic :: Scientific/Engineering :: Mathematics
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

BSD 4-Clause (the original "BSD with advertising clause" license) —
see `LICENSE`. Copyright (c) 2026 ETH Zürich and the apxchol contributors.

## 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`.
