Skip to content
Symi Docs
Python
On this page

Cylindrical algebraic decomposition

A CylindricalAlgebraicDecomposition partitions Rn\mathbb{R}^n into finitely many cells on each of which every input polynomial has constant sign, with an exact sample point in each cell. It is built over a list of polynomials in a declared variable order. By default it uses the Brown projection — a smaller, faster operator than the complete Lazard projection — and verifies its result is well-oriented, falling back to the complete Lazard projection on any failure, so the output is always a correct sign-invariant CAD, never an orientation decline. It raises only when an input lies outside Q[variables]\mathbb{Q}[\text{variables}] or when the exact arithmetic cannot co-reside a sample point's coordinates in one extension.

Declaring equational constraints (indices into the polynomial list, via the constructor's equational_constraints argument) selects the equational-constraint CAD instead: a smaller decomposition that is sign-invariant for the non-constraint polynomials on the constraint variety (where every declared constraint is zero), the lever that makes constrained queries tractable.

The accessors below index the full-dimensional cells — the cells that actually partition Rn\mathbb{R}^n — by an ordinal 0 .. cell_count. Every sign is decided exactly by the real-algebraic-number layer; the float sample points are a numeric view, never a decision.

Construction#

new#

Not exposed by the Python bindings. Available as ContextConstructor.new in WASM / JavaScript.

Construct the CAD of the polynomials in the given variable order x1,…,xnx_1,\ldots,x_n; projection eliminates xnx_n first). With an empty equational_constraints list this is the full sign-invariant CAD (Brown fast path with Lazard fallback); listing indices into polynomials selects the equational-constraint CAD on the variety where those polynomials vanish. Raises when any polynomial is outside Q[variables]\mathbb{Q}[\text{variables}] or the decomposition cannot be formed. Notes: the WASM signature is new cylindrical_algebraic_decomposition(polynomials: ExpressionLike[], variables: string[], equational_constraints?: number[]).

Accessors#

cell_count#

The number of full-dimensional cells partitioning Rn\mathbb{R}^n.

CylindricalAlgebraicDecomposition method

cell_count() -> int

The number of full-dimensional cells partitioning Rn\mathbb{R}^n.

cell_sample_point#

The coordinates of the full cell's sample point as floats — a numeric view via the multi-precision evaluator, not a decision.

CylindricalAlgebraicDecomposition method

cell_sample_point(index: int) -> list[float]

The coordinates of the full cell's sample point as floats — a numeric view via the multi-precision evaluator, not a decision.

cell_sign_vector#

The exact sign (−1-1, 00, or +1+1) of each input polynomial on the full cell, in input order.

CylindricalAlgebraicDecomposition method

cell_sign_vector(index: int) -> list[int]

The exact sign (−1-1, 00, or +1+1) of each input polynomial on the full cell, in input order.

cell_kind#

"section" or "sector" — whether the cell is a root section or an open interval in its top variable.

CylindricalAlgebraicDecomposition method

cell_kind(index: int) -> str

"section" or "sector" — whether the cell is a root section or an open interval in its top variable.

cell_dimension#

The geometric dimension of the full cell as a subset of Rn\mathbb{R}^n (the number of sector coordinates along its cylindrical stack).

CylindricalAlgebraicDecomposition method

cell_dimension(index: int) -> int

The geometric dimension of the full cell as a subset of Rn\mathbb{R}^n (the number of sector coordinates along its cylindrical stack).

projection_operator_used#

The projection operator the decomposition was built with: "brown" for the well-oriented fast path, "lazard" when the well-orientedness guard forced the complete fallback, "equational_constraint" for an equational-constraint CAD.

CylindricalAlgebraicDecomposition method

projection_operator_used() -> str

The projection operator the decomposition was built with: "brown" for the well-oriented fast path, "lazard" when the well-orientedness guard forced the complete fallback, "equational_constraint" for an equational-constraint CAD.

Example#

Decompose the plane along one circle and inspect a cell.

Python
import symi

x = symi.symbol("x")
y = symi.symbol("y")
decomposition = symi.CylindricalAlgebraicDecomposition(
    [x**2 + y**2 - 1], ["x", "y"]
)

print(decomposition.cell_count())
print(decomposition.cell_kind(0))
print(decomposition.cell_sample_point(0))

Additional API#

CylindricalAlgebraicDecomposition#

CylindricalAlgebraicDecomposition constructor

CylindricalAlgebraicDecomposition(
    expressions: Iterable[ExpressionLike],
    variables: Iterable[VariableLike],
    equational_constraints: list[int] = [],
)

Decompose real space into sign-invariant cells for the given polynomials, in the given variable order.

Symi documentation · Python