Cylindrical algebraic decomposition
A CylindricalAlgebraicDecomposition partitions 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 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 — 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 ;
projection eliminates 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
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 .
CylindricalAlgebraicDecomposition method
cell_count() -> intThe number of full-dimensional cells partitioning .
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 (, , or ) of each input polynomial on the full cell, in input order.
CylindricalAlgebraicDecomposition method
cell_sign_vector(index: int) -> list[int]The exact sign (, , or ) 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 (the number of sector coordinates along its cylindrical stack).
CylindricalAlgebraicDecomposition method
cell_dimension(index: int) -> intThe geometric dimension of the full cell as a subset of (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() -> strThe 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.
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.