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 for the full API.

Install and run

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

python -m pip install algroots

Solve a polynomial system

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.

Preserve branches and poles

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

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 and Reading Results.

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

Exact algebra and advanced solving

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 and continuation and monodromy.

Examples and documentation

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

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

Start with Quick Start, Supported Problems, Support Matrix and Reading Results. The documentation index links every topic, including the API reference, limitations and troubleshooting.

Development

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 and Contributing.

License

The package is distributed under the GPL-3.0 license.