Metadata-Version: 2.4
Name: semialg
Version: 1.1.0
Summary: Exact real algebraic and semialgebraic geometry in Python: CAD, quantifier elimination, semialgebraic solving, decomposition, integration, and measure
Author-email: Bhuvanesh Bhatt <bhuvaneshbhatt@gmail.com>
License-Expression: GPL-3.0-only
Project-URL: Homepage, https://github.com/BhuvaneshBhatt/semialg
Project-URL: Repository, https://github.com/BhuvaneshBhatt/semialg
Project-URL: Issues, https://github.com/BhuvaneshBhatt/semialg/issues
Project-URL: Documentation, https://github.com/BhuvaneshBhatt/semialg/tree/main/docs
Keywords: symbolic mathematics,computer algebra,semialgebraic geometry,real algebraic geometry,cylindrical algebraic decomposition,CAD,quantifier elimination,polynomial systems,real root isolation,exact computation,certified computation,symbolic integration,semialgebraic optimization,SymPy
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.11
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: sympy>=1.12
Requires-Dist: python-flint>=0.9.0
Requires-Dist: exprtest>=0.1.0
Provides-Extra: test
Requires-Dist: pytest>=8; extra == "test"
Requires-Dist: pytest-cov>=5; extra == "test"
Requires-Dist: hypothesis>=6; extra == "test"
Requires-Dist: matplotlib>=3.8; extra == "test"
Requires-Dist: nbformat>=5; extra == "test"
Requires-Dist: nbclient>=0.10; extra == "test"
Requires-Dist: ipykernel>=6; extra == "test"
Requires-Dist: PyYAML>=6; extra == "test"
Provides-Extra: dev
Requires-Dist: pytest>=8; extra == "dev"
Requires-Dist: pytest-cov>=5; extra == "dev"
Requires-Dist: hypothesis>=6; extra == "dev"
Requires-Dist: matplotlib>=3.8; extra == "dev"
Requires-Dist: ruff>=0.4; extra == "dev"
Requires-Dist: nbformat>=5; extra == "dev"
Requires-Dist: nbclient>=0.10; extra == "dev"
Requires-Dist: ipykernel>=6; extra == "dev"
Requires-Dist: PyYAML>=6; extra == "dev"
Provides-Extra: docs
Requires-Dist: mkdocs>=1.6; extra == "docs"
Provides-Extra: notebooks
Requires-Dist: matplotlib>=3.8; extra == "notebooks"
Requires-Dist: jupyter>=1; extra == "notebooks"
Requires-Dist: nbclient>=0.10; extra == "notebooks"
Requires-Dist: ipykernel>=6; extra == "notebooks"
Provides-Extra: release
Requires-Dist: build>=1.2; extra == "release"
Requires-Dist: twine>=6; extra == "release"
Dynamic: license-file

# semialg

`semialg` is a Python package for exact computational semialgebraic  and real algebraic geometry. It combines cylindrical algebraic decomposition (CAD), quantifier elimination (QE), exact real-algebraic arithmetic, polynomial-system and algebraic-decomposition methods, and specialized algorithms for solving, decision problems, geometric analysis, optimization, and integration.

The package has certified paths that prefer an exact answer (or an explicit failure) and a numerical approximation is not treated as proof.

## Why use semialg?

Use semialg when the distinction between a plausible numerical answer and a mathematically certified answer matters. It is especially useful when a problem mixes polynomial equations and inequalities, Boolean conditions, parameters, exact algebraic numbers, or global questions such as feasibility, equivalence, projection, optimization, topology, or measure. Specialized algebraic and geometric methods handle inexpensive cases first; CAD and QE provide exact fallback machinery for supported real-polynomial formulas.

If you primarily need floating-point nonlinear optimization, general numerical transcendental solving, or large numerical geometry rather than exact semialgebraic computation, established numerical libraries will usually be a better fit. Consider SciPy for numerical optimization and nonlinear systems, SymPy/mpmath for numerical transcendental root finding, Shapely for planar computational geometry, and Trimesh for numerical 3-D mesh geometry. See the [capability matrix](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/feature_matrix.md) and [limitations](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/limitations.md) before choosing an algorithm.

## Install

```bash
python -m pip install semialg
```

For development:

```bash
python -m pip install -e .[dev]
```

## Quick start

```python
import sympy as sp
from semialg import equivalent, implies, is_satisfiable

x, y = sp.symbols("x y", real=True)

assert is_satisfiable((x**2 + y**2 <= 1) & (x > 0) & (y > 0), [x, y]) is True
# True

assert implies(x > 1, x**2 > 1, [x]) is True
# True

assert equivalent(x**2 <= 1, (x >= -1) & (x <= 1), [x]) is True
# True
```

First-order formulas can also be built directly with semialg's symbolic
quantifiers:

```python
from semialg import Exists, ForAll
from semialg.solve import reduce_complete_expr

statement = ForAll(x, Exists(y, sp.Eq(x + y, 0)))
assert reduce_complete_expr(statement) is sp.true
# True
```

Optimization and integration use the same exact-first model:

```python
from semialg import semialgebraic_minimize, semialgebraic_measure

opt = semialgebraic_minimize(x**2 + y**2, x + y >= 1, [x, y], return_result=True)
assert opt.value == sp.Rational(1, 2)
# 1/2

assert semialgebraic_measure(x**2 + y**2 <= 1, [x, y]) == sp.pi
# pi
```

Composite Boolean regions are interpreted geometrically through CAD rather than atom-by-atom rewriting. The same disjoint CAD-cell decomposition is used by multidimensional measure and integration, so overlapping unions are not double-counted and internal Boolean seams are not reported as boundaries.

The canonical symbolic region API is `SemialgebraicRegion`; build a `CADRegion` only when repeated point-location, topology, cell-complex, or CAD-integration queries justify reusing one decomposition:

```python
from semialg import SemialgebraicRegion

disk_region = SemialgebraicRegion(x**2 + y**2 <= 1, (x, y))
cad_region = disk_region.as_cad_region()

location = cad_region.locate_point((0, 0))
complex_ = cad_region.cell_complex()
assert location.selected
assert complex_.euler_characteristic() == 1
```

See the [region representation guide](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/region_representations.md), [CAD reuse guide](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/cad_reuse.md), and [exact-versus-numerical guide](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/exact_vs_numerical_regions.md). The [API surface policy](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/architecture/api_surface.md) distinguishes primary root-level names from expert submodule APIs and internal implementation details.

Parameter-dependent region integrals can return certified guarded answers:

```python
a = sp.Symbol("a", real=True)
from semialg import integrate_over_region

parametric = integrate_over_region(
    x,
    (x >= 0) & (x <= a),
    [x],
    parameters=[a],
    return_stratified=True,
)
assert parametric.select({a: 2}) == 2
# 2
assert parametric.select({a: -1}) == 0
# 0
```

Parametric optimization and range APIs keep exact quantified relations by default. Pass `eliminate_quantifiers=True` together with `return_stratified=True` when a quantifier-free relation is worth the additional CAD/QE cost. Common affine one-dimensional parameter families are reconstructed directly before a second CAD/QE is attempted.

The complete-QE path also has a conservative structural presolver and automatic CAD ordering. Safe affine equalities and linear innermost existential blocks are eliminated before CAD; Brown-style ordering is applied only within semantically interchangeable free/quantifier blocks. Projection-set scoring is available explicitly through `suggest_cad_variable_order(..., strategy="projection")`.

```python
from semialg.heuristics import suggest_cad_variable_order
from semialg.presolve import presolve_semialgebraic

presolved = presolve_semialgebraic(sp.And(sp.Eq(y, x + 1), y > 0), [x, y], eliminate=[y])
assert presolved.formula == (x > -1)
# presolved.formula == (x > -1)

score = suggest_cad_variable_order([x**2 + y**4, x * y + 1], [x, y])
assert set(score.order) == {x, y}
```

Univariate parameter-dependent integrals can use algebraic CAD root functions as moving endpoints. For example, the measure of `x**2 <= a` is stratfied exactly as zero for `a <= 0` and the distance between the two ordered roots for `a > 0`; specialization gives `4` at `a=4` and `6` at `a=9`.

High-level geometric queries compose the same certified backends:

```python
from semialg import (
    argmin_set,
    bounding_box,
    centroid,
    connected_components,
    diameter,
    distance_to_region,
    is_compact,
    minkowski_sum,
    semialgebraic_image,
    singular_locus,
    tangent_cone,
    width,
)

u = sp.Symbol("u", real=True)
assert semialgebraic_image(x, (x >= -1) & (x <= 2), [x], image_variables=[u]) == sp.And(
    u >= -1, u <= 2
)
# (u >= -1) & (u <= 2)

assert bounding_box((x >= -1) & (x <= 2), [x]) == {x: (-1, 2)}
# {x: (-1, 2)}

assert distance_to_region((2,), (x >= 0) & (x <= 1), [x]) == 1
# 1

assert singular_locus(y**2 - x**3, [x, y]).subs({x: 0, y: 0}) is sp.true
assert tangent_cone(y**2 - x**3, {x: 0, y: 0}, [x, y]).certified
# Exact ideal-theoretic cone for multiple generators; cancellation terms are retained.
assert tangent_cone((x**2 + y**3, x**2 - y**3), {x: 0, y: 0}, [x, y]).ideal_generators
# Eq(d_y**2, 0)
```

Derived geometry APIs expose common exact constructions without duplicating algorithms:

```python
interval = (x >= 0) & (x <= 2)

assert argmin_set(x**2, interval, [x]) == sp.And(x >= 0, x <= 2, sp.Eq(x**2, 0))
# (x >= 0) & (x <= 2) & Eq(x**2, 0)

assert diameter(interval, [x]) == 2
# 2

assert width(interval, (1,), [x]) == 2
# 2

assert is_compact(interval, [x]) is True
# True

assert connected_components((x < 0) | (x > 0), [x]) == (x < 0, x > 0)
# (x < 0, x > 0)

assert centroid(interval, [x]) == {x: 1}
# {x: 1}
```

The same layer includes set relations (`is_subset`, `is_equal`, `is_disjoint`, `intersects`), level/sublevel/superlevel sets, nearest/closest points, moment/covariance/inertia matrices, affine transforms and Minkowski sums, support functions, directional widths, and algebraic `is_smooth` / `is_singular` / `tangent_dimension` conveniences. Operations such as Minkowski sums and general affine images remain exact existential-QE problems and can therefore inherit CAD complexity.


Region topology uses CAD semantics even for atomic polynomial inequalities; compact direct formulas are used only after cell-wise equivalence verification. `region_dimension` is likewise exact and is read from selected CAD-cell dimensions. Free parameters are preserved by `semialgebraic_image` when source variables are explicit, and all geometry point/string inputs use contextual symbol resolution.

`is_path_connected` is an exact decision through CAD connectivity. `path_between` returns an explicit piecewise-linear path in the certified 1-D case and a certified CAD cell/connector chain in higher dimensions; full Canny/Basu-Pollack-Roy roadmap parameterization is outside this API.

## Applied workflows

`semialg.applications` provides thin workflows built on the certified core:

- **Robust parameter analysis** — derive exact parameter regions for existential feasibility or universal satisfaction.
- **Symbolic-math validation** — certify identities, formula equivalence, and proposed function ranges.
- **Optimization benchmark oracle** — produce certified exact optima for checking numerical optimizers.
- **Polynomial control stability** — derive exact strict Hurwitz-stability regions from characteristic polynomials.
- **Polynomial safety invariants** — certify initiation, inductiveness, and unsafe-state exclusion for discrete polynomial systems.
- **Polynomial response surfaces** — compute exact extrema, ranges, gradients, and threshold regions for polynomial surrogate models.
- **Polynomial model comparison** — certify worst-case discrepancy, dominance, and equivalence over a domain.
- **Parameter regime analysis** — partition parameter space by solvability or real-root count.
- **Polynomial probability** — integrate exact polynomial densities over semialgebraic events and supports.

See [`docs/applications.md`](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/applications.md). Core operations such as `function_range`, `semialgebraic_measure`, integration, optimization, CAD, and QE remain in the core namespace rather than being duplicated under `applications`.

## Worked examples

The documentation includes a [worked example gallery](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/examples/index.md) with executable examples for projection/QE, exact ranges and optimization, topology, moments, singular geometry, convex operations, distances, and parameterized algebraic integration.

## What semialg provides

- **Decision and QE:** satisfiability, tautology, implication, equivalence, CAD and quantifier elimination.
- **Specialized real algebraic decisions:** certified positive-dimensional equality feasibility, replayable algebraic decomposition, exact polynomial nonnegativity, and one-sided exact witness search.
- **Solving and sampling:** an exact solver with affine presolve, Boolean/incidence decomposition, univariate and linear fast paths, zero-dimensional RUR, Groebner presolve, and CAD/QE fallback, plus structured witnesses and samples.
- **Algebraic roots and parameters:** exact root isolation, certified algebraic root functions, root classification, and parameter-stratified results.
- **Toric and lattice algebra:** saturated integer kernels, lattice and toric ideals, Laurent-monomial elimination, and exact Markov bases.
- **Regions:** Boolean region operations, exact set relations/properties, topology, CAD connected components, transforms, standard geometric regions, and CAD-derived geometry.
- **Geometric queries:** exact projection/image/preimage/fibers, extrema sets, bounding boxes, distances/diameter, support/width, transforms/Minkowski sums, staged exact convexity certificates, connectivity/property predicates, Euler characteristic, moments, singular loci, tangent spaces, and tangent cones.
- **Optimization and ranges:** exact polynomial optimization, KKT/active-set analysis, global certification, and semialgebraic image/range computation.
- **Integration and moments:** ambient and intrinsic measure, region integrals, moments, centroids, and covariance.
- **Computational algebraic geometry:** exact polynomial-system solving, Gröbner/elimination methods, rational univariate representations, algebraic decomposition, singular loci and tangent geometry, with toric and lattice-ideal constructions.

See [feature matrix](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/feature_matrix.md) for more detailed capability summary and [limitations](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/limitations.md) for important scope boundaries.

## Semialgebraic geometry

`semialg` represents and analyzes sets defined by polynomial equations and inequalities and Boolean combinations of those constraints. Geometry operations use exact real-algebraic methods and specialized region algorithms where available, with CAD and quantifier elimination providing general exact machinery for supported polynomial problems.

### Regions and geometric operations

`SemialgebraicRegion` is the primary symbolic region abstraction. Canonical region classes provide structured representations for common geometries, while `CADRegion` supports repeated cell-level queries when reusing a decomposition is worthwhile. Region operations include Boolean set operations, membership and set relations, dimension, boundary/interior/closure queries, bounding boxes, distances, extrema sets, support and width, and derived moment quantities.

### Region sampling, measure, and centroid

Canonical geometry objects provide `sample_point()` and `sample_points()` for certified representative points, and `random_point()` and `random_points()` for seeded random sampling. Supported bounded canonical regions are sampled uniformly with respect to intrinsic Euclidean/Hausdorff measure. `Geometry.measure()` uses intrinsic measure by default; `measure(measure_dimension="ambient")` instead computes ambient Lebesgue measure. `Geometry.centroid()` uses the same uniform intrinsic measure.

### Topology and connectivity

Topology is computed from exact semialgebraic structure rather than numerical meshing. The package provides region dimension, connected components, connectivity and path-connectivity decisions, Euler characteristic, cell-complex access, singular loci, tangent spaces, and tangent cones. Higher-dimensional `path_between` results certify a CAD cell/connector chain rather than constructing a general roadmap parameterization.

### Transformations

Exact image, preimage, projection, and fiber operations are available for supported semialgebraic maps. Affine transformations preserve structured geometry when a canonical result can be certified; more general images and Minkowski sums are represented as existential semialgebraic problems and may require QE/CAD. Real-geometry affine entry points reject certifiably non-real map data at the input boundary.

### Function analysis via function graphs

Semialgebraic function analysis is composition-aware for functions whose graphs can be represented exactly by supported polynomial conditions. Nested radicals/rational powers, `Abs`, `sign`, `Heaviside`, `Min`/`Max`, finite `Piecewise`, and real `re`/`im`/`conjugate` wrappers can be algebraized when their real-domain side conditions are certifiable; unsupported graphs are declined.


## Primary and specialist APIs

The package root is the everyday mathematical interface, while expert-level/specialist algorithms and certificate-building workflows live in their owning namespaces instead of being duplicated at `semialg.*`. For example, use `semialg.parameters.root_count_conditions`, `semialg.roadmaps.roadmap`, `semialg.topology.semialgebraic.triangulate_region`, `semialg.parametric_geometry.bounded_parametric_cover`, and `semialg.map_degree.parametric_map_degree` when those lower-level functions are needed. See [API namespaces](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/api_namespaces.md).

## Documentation

- [Benchmark and conformance suite](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/benchmarks.md) — published Wilson CAD and TTICAD corpora plus parameterized Gröbner families; includes commands for reproducible conformance/performance runs.

New users should start with **[Getting started](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/getting_started.md)** and then follow the task-oriented links in the **[documentation index](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/index.md)**.

Important conceptual material:

- [Introduction to semialgebraic geometry](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/semialgebraic_geometry/introduction.md)
- [Exactness and certification](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/concepts/exactness_and_certification.md)
- [Performance guide](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/performance.md)
- [Errors and failure modes](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/errors_and_failure_modes.md)
- [Symbol handling](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/symbol_handling.md)
- [Region invariants](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/guides/region_invariants.md)
- [API overview](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/api_overview.md)
- [Toric and lattice algebra](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/toric_algebra.md)

A progressive executable tutorial is available in [`notebooks/semialg_demo.ipynb`](https://github.com/BhuvaneshBhatt/semialg/blob/main/notebooks/semialg_demo.ipynb).

## Exact vs certified

A result being symbolic is not by itself a certificate. semialg distinguishes between exact representations, certified conclusions, candidate/heuristic information, and explicitly numerical approximations. See [Exactness and certification](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/concepts/exactness_and_certification.md).

## Development

```bash
ruff format .
ruff check .
pytest -m "not slow"
pytest -m slow --durations=20
pytest -m performance --durations=20
python scripts/verify_source_quality.py
mkdocs build --strict
pytest -q -m slow tests/test_documentation_example_gallery.py
```

See the [architecture guide](https://github.com/BhuvaneshBhatt/semialg/blob/main/docs/architecture/design.md) for implementation structure.

## References

- Michel Coste, *An Introduction to Semialgebraic Geometry*.

## License

See the [LICENSE](https://github.com/BhuvaneshBhatt/semialg/blob/main/LICENSE).
