Metadata-Version: 2.5
Name: algroots
Version: 0.2.0
Summary: Exact and approximate methods for solving zero-dimensional polynomial and algebraic systems.
Project-URL: Homepage, https://github.com/BhuvaneshBhatt/algroots
Project-URL: Documentation, https://github.com/BhuvaneshBhatt/algroots/tree/main/docs
Project-URL: Repository, https://github.com/BhuvaneshBhatt/algroots.git
Project-URL: Issues, https://github.com/BhuvaneshBhatt/algroots/issues
Project-URL: Changelog, https://github.com/BhuvaneshBhatt/algroots/blob/main/CHANGELOG.md
Author-email: Bhuvanesh Bhatt <bhuvaneshbhatt@gmail.com>
License-Expression: GPL-3.0-only
License-File: LICENSE
Keywords: algebraic-equations,algebraic-geometry,algebraic-numbers,border-basis,groebner-basis,numerical-roots,polynomial-systems,radicals,rational-functions,rational-univariate-representation
Classifier: Development Status :: 3 - Alpha
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
Requires-Dist: algrecognize>=0.1.1
Requires-Dist: mpmath<2,>=1.3
Requires-Dist: python-flint<1,>=0.9
Requires-Dist: sympy<2,>=1.13
Provides-Extra: benchmark
Requires-Dist: pytest-benchmark>=5.2; extra == 'benchmark'
Requires-Dist: pytest>=8; extra == 'benchmark'
Provides-Extra: dev
Requires-Dist: ruff>=0.12; extra == 'dev'
Provides-Extra: mutation
Requires-Dist: mutmut>=3; extra == 'mutation'
Provides-Extra: release
Requires-Dist: build>=1.2; extra == 'release'
Requires-Dist: twine>=6; extra == 'release'
Provides-Extra: test
Requires-Dist: hypothesis>=6; extra == 'test'
Requires-Dist: pytest-cov>=6; extra == 'test'
Requires-Dist: pytest>=8; extra == 'test'
Description-Content-Type: text/markdown

# algroots

`algroots` solves **exact polynomial and supported algebraic equations with finite complex solution sets (zero-dimensional systems)**. It combines exact Gröbner and quotient-algebra structure with arbitrary-precision FLINT/Arb root extraction. It also provides exact rational univariate representations, border bases, isolated-root certificates and targeted deflation.

Use `polysolve` for polynomials and `algsolve` for rational functions, principal rational powers and nested radicals. For now, coefficients must be exact: use `sp.Rational(1, 10)`, rather than `0.1`. `algroots` does not support positive-dimensional varieties, inequalities, noisy coefficients or transcendental equations.

## Public API

Use `polysolve` or `algsolve` from the package root. Manual certification, quotient algebra, RURs, border bases and continuation tools use their public submodules. See the [namespace map](docs/api.md#root-and-specialized-namespaces) for the full API.

## Install and run

Python 3.11 or newer is required. The dependencies include SymPy, mpmath, python-flint and algrecognize.

```bash
python -m pip install algroots
```

## Solve a polynomial system

<!-- algroots: execute -->
```python
import sympy as sp
from algroots import polysolve

x, y = sp.symbols("x y")
result = polysolve((x**2 + y**2 - 3, x * y - 1), (x, y), digits=40, recognize=False)
assert len(result.roots) == result.geometric_solution_count == 4
print(result.roots)
print(result.completeness)
```

In the result each tuple follows the supplied variable order. `.roots` stores distinct geometric points with aligned per-root metadata. Use `root_mode="with_multiplicity"` for repeated-root iteration and `.output_roots`; `.multiplicities` reports established local multiplicities. Results use canonical coordinate ordering, with `.ordering` distinguishing exact ordering from numerical fallback. `root_order="required"` requires exact ordering within the proof budgets. `digits` requests output precision; working precision may increase, and `verification_digits` controls the numerical residual standard. A small residual by itself is not an exact root or completeness proof.

The automatic dispatch applies guarded exact presolve, deterministic ordering and a grevlex (graded reverse lexicographic) Gröbner basis. Action and RUR share quotient work; conversion to lexicographic with FGLM occurs only when needed. Cost hints preserve exact fallback checks. See [Choosing a Backend](docs/choosing-a-backend.md).

## Preserve branches and poles

<!-- algroots: execute -->
```python
import sympy as sp
from algroots import algsolve

x = sp.Symbol("x")
result = algsolve((sp.sqrt(x) - (x - 2),), (x,), digits=40, recognize=False)
assert len(result.roots) == 1
assert abs(result.roots[0][0] - 4) < sp.Rational(1, 10**30)
```

Squaring also produces `x=1`, which fails the original principal-square-root equation. `algsolve` filters such candidates and retains denominator restrictions. Obviously, it cannot recover domain information already removed by SymPy before the input is supplied.

## Certify roots and inspect multiplicities

<!-- algroots: execute -->
```python
import sympy as sp
from algroots import polysolve

x = sp.Symbol("x")
result = polysolve((x**2,), (x,), recognize=False, certify="required")
assert len(result.roots) == 1
assert result.total_multiplicity == 2 and not result.is_radical
certificate = result.root_certifications[0].certificate
assert certificate.multiplicity == 2 and certificate.verify()
```

`certify="auto"` records best-effort proof attempts; `certify="required"` raises when a proof cannot be established. Automatic boxes currently require rational coefficients and a globally finite ideal. Exact-point certification also supports algebraic coefficients. Dimension, refinement and box-attempt budgets are explicit.

Recognition is a different operation. By default, solvers attempt exact coordinate recognition through `algrecognize`; successful jointly certified tuples appear in `recognized_roots`. Recognition failure leaves the numerical result available. `recognize=False` disables that post-processing. See [Certification Workflow](docs/certification-workflow.md) and [Reading Results](docs/reading-results.md).

| Evidence | What it establishes |
|---|---|
| Residual diagnostics | Numerical consistency at the verification standard |
| `completeness.status == "conditional"` | Exact finite count/structure, with numerical extraction assumptions |
| Exact isolated-root certificate | The point satisfies the original equations, is isolated, and has the reported rank/multiplicity |
| Certified bounded recovery | Distinct exact endpoint proofs account for the exact finite-root count |
| Numerical paths / monodromy stopping | Numerical or statistical evidence; no certified path or infinity accounting |

Per-root certificates and recognition don't automatically upgrade the result-wide completeness status.

## Exact algebra and advanced solving

| Task | API | Guide |
|---|---|---|
| Quotient basis, normal forms, matrices, traces | `QuotientAlgebra` | [Quotient tools](docs/quotient-tools.md) |
| Exact RUR and exact algebraic points | `compute_rational_univariate_representation`, `solve_rur_representation` | [RUR](docs/rational-univariate-representation.md) |
| Exact rational border bases | `compute_border_basis`, `compute_border_basis_linear` | [Border bases](docs/exact-border-bases.md) |
| Singular-root proof and exact local deflation | `certify_isolated_root`, `deflate_isolated_root` | [Singular certification](docs/singular-certification-and-charts.md) |
| Bounded endgame/deflation/chart recovery | `polysolve(method="homotopy", homotopy_recovery=True)` | [Recovery](docs/recovery-workflow.md) |
| Numerical projective tracking | `projective_homotopy`, `track_projective_path` | [Chart switching](docs/singular-certification-and-charts.md) |
| Seeded experimental monodromy | `discover_monodromy_orbit` | [Monodromy](docs/continuation-and-monodromy.md) |

Ordinary `method="homotopy"` targets regular square systems whose required Bézout paths reach finite nonsingular endpoints. Recovery is opt-in, sequential, rational-coefficient and bounded. It adds a finite quotient for proof accounting, preserves successful endpoint proofs across retries, and reports unresolved paths. Neither of those modes certifies numerical paths or roots at infinity. Homotopy is not selected by `auto`.

## Numerical precision and stopping

Numerical precision and integer budgets follow a common contract: nonzero coordinate components are preserved, root comparisons are relative to coordinate scale, and univariate Arb retries respect the working precision ceiling. Monodromy curvature stopping is a heuristic and gives no completeness evidence. See [precision and conditioning](docs/precision-and-conditioning.md) and [continuation and monodromy](docs/continuation-and-monodromy.md).

## Examples and documentation

The [examples catalog](examples/README.md) contains 16 scripts covering solving, branch filtering, recognition, quotient caches, RUR, algebraic fields, multiplicities, clusters, diagnostics, border bases, deflation, recovery, charts, monodromy and failures.

```bash
python examples/run_all.py
python examples/run_all.py 07_multiplicity_and_boxes.py 15_limits_and_failures.py
```

Start with [Quick Start](docs/quick-start.md), [Supported Problems](docs/supported-problems.md), [Support Matrix](docs/feature-support-matrix.md) and [Reading Results](docs/reading-results.md). The [documentation index](docs/index.md) links every topic, including the [API reference](docs/api.md), [limitations](docs/limitations.md) and [troubleshooting](docs/troubleshooting.md).

## Development

```bash
python -m pytest
python -m ruff check .
python -m ruff format --check .
```

Tests execute marked documentation and every catalog example, check navigation and API defaults, compare exact algebra against independent oracles, and exercise adversarial/resource limits. Benchmarks retain exact correctness checks but do not enforce wall-clock thresholds. See [Testing and Validation](docs/testing-and-validation.md) and [Contributing](CONTRIBUTING.md).

## License

The package is distributed under the [GPL-3.0 license](https://github.com/BhuvaneshBhatt/asymptotic/blob/main/LICENSE).
