CylindricalDecomposition

CylindricalDecomposition[ineqs,{x1,x2,}]

finds a decomposition of the region represented by the inequalities ineqs into cylindrical parts whose directions correspond to the successive xi.

CylindricalDecomposition[ineqs,{x1,x2,},op]

finds a decomposition of the result of applying the topological operation op to the region represented by the inequalities ineqs.

Details and Options

  • CylindricalDecomposition assumes that all variables are real.
  • Lists or logical combinations of inequalities can be given.
  • CylindricalDecomposition returns inequalities whose bounds in general involve algebraic functions.
  • The topological operation op can be one of:
  • "Boundary"boundary of the solution set
    "Closure"closure of the solution set
    "Interior"interior of the solution set
    "Exterior"exterior of the solution set
    "ClosureOfInterior"closure of the interior of the solution set
    "InteriorOfClosure"interior of the closure of the solution set
    "Components"connected components of the solution set

Examples

open allclose all

Basic Examples  (2)

Find a cylindrical decomposition of the unit disc:

Find a cylindrical decomposition of the boundary of the unit disc:

Scope  (10)

Basic Uses  (5)

For univariate polynomials, the result consists of intervals:

In general, individual points can occur:

This is the form for any logical combination as well:

For multivariate polynomials, the result is in cylinder form :

In general, several cylinders will result:

Plot the individual cylinders using RegionPlot:

By changing the order of variables, the cylinders take the form :

Plot the individual cylinders:

Here cylinders of dimensions 0, 2, and 1 occur in the result:

Three- and four-dimensional decompositions:

Topological Operations  (5)

Find decompositions of the solution region and its boundary:

Find decompositions of the solution region and its closure:

Find decompositions of the solution region and its interior:

Find decompositions of the solution region and its exterior:

Find decompositions of the solution region and its connected components:

Generalizations & Extensions  (4)

CylindricalDecomposition also allows quantified formulas:

Coefficients can include real algebraic numbers:

Coefficients can include real exact transcendental numbers:

Functions can be real algebraic:

Options  (1)

WorkingPrecision  (1)

This computation takes a long time due to high degrees of numeric coefficients:

This finds a decomposition using WorkingPrecision->1000, but the result may be incorrect:

Applications  (2)

Find the connected components of an algebraic curve:

Find the connected components of a region:

Properties & Relations  (8)

Use RegionPlot to visualize 2D semialgebraic sets:

Use RegionPlot3D to visualize 3D semialgebraic sets:

Resolve performs quantifier elimination and may avoid computing cylindrical decomposition:

Reduce in addition deals with different domains and transcendental functions:

Use FindInstance to find points that satisfy equations and inequalities:

SemialgebraicComponentInstances will give sample points in each cylinder:

CylindricalDecomposition merges several cylinders to get a more compact representation:

GenericCylindricalDecomposition will compute the full-dimensional part only:

The output and input are equal as sets:

Points are simultaneously inside or outside of the sets:

Possible Issues  (2)

CylindricalDecomposition requires exact, infiniteprecision input:

Rationalize will convert inexact numbers to exact ones:

In general, the output can be in a nested and more compact form:

Flatten the result into disjunctive normal form without splitting the inequalities:

Neat Examples  (1)

Semialgebraic sets are quite general:

Introduced in 2003
 (5.0)
 |
Updated in 2017
 (11.2)