Cylindrical Algebraic Decomposition I: The Basic Algorithm

DOI10.1137/0213054zbMath0562.14001OpenAlexW2067705970MaRDI QIDQ5187396

George E. Collins, Dennis S. Arnon, Scott McCallum

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213054

zbMATH Keywords

algorithmcomputational geometryreal algebraic geometrydecision procedurecadzeros of the polynomialscylindrical algebraic decomposition of the Euclidean r-spacepairs of adjacent cells

Mathematics Subject Classification ID

Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Software, source code, etc. for problems pertaining to algebraic geometry (14-04) Algorithms in computer science (68W99) Real algebraic and real-analytic geometry (14Pxx)

Related Items (81)

Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks ⋮ Geometry and topology of parameter space: Investigating measures of robustness in regulatory networks ⋮ On pole assignment of linear systems by gain output feedback ⋮ Computer algebra: Past and future ⋮ Upper bounds for the Hausdorff dimension and stratification of an invariant set of an evolution system on a Hilbert manifold ⋮ An algorithm for generalized point location and its applications ⋮ On mechanical quantifier elimination for elementary algebra and geometry ⋮ A bibliography of quantifier elimination for real closed fields ⋮ An improved projection operation for cylindrical algebraic decomposition of three-dimensional space ⋮ An adjacency algorithm for cylindrical algebraic decompositions of three- dimensional space ⋮ A cluster-based cylindrical algebraic decomposition algorithm ⋮ Parallel algorithms for arrangements ⋮ Polygonization of implicit surfaces ⋮ Maxwell's conjecture on three point charges with equal magnitudes ⋮ Computational issues in solid boundary evaluation ⋮ A complete algorithm for automated discovering of a class of inequality-type theorems ⋮ A polynomial-time algorithm for the topological type of real algebraic curve ⋮ Wu's method and its application to perspective viewing ⋮ An approximate characterisation of the set of feasible trajectories for constrained flat systems ⋮ A multi-level geometric reasoning system for vision ⋮ Algebraic decomposition of regular curves ⋮ Résolution du problème de l'ellipse et du cercle par l'algorithme de Hörmander ⋮ A refutational approach to geometry theorem proving ⋮ On the topology and isotopic meshing of plane algebraic curves ⋮ Conormal spaces and Whitney stratifications ⋮ Non-monotonic spatial reasoning with answer set programming modulo theories ⋮ Multiphase until formulas over Markov reward models: an algebraic approach ⋮ A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces ⋮ Analyzing ultimate positivity for solvable systems ⋮ On the topology of real algebraic plane curves ⋮ Computing integrals over polynomially defined regions and their boundaries in 2 and 3 dimensions ⋮ Computing with Tarski formulas and semi-algebraic sets in a web browser ⋮ Improved mixing condition on the grid for counting and sampling independent sets ⋮ Combinatorial complexity bounds for arrangements of curves and spheres ⋮ Geometric reasoning with logic and algebra ⋮ Parallel computation of real solving bivariate polynomial systems by zero-matching method ⋮ An algebraic method to calculate parameter regions for constrained steady-state distribution in stochastic reaction networks ⋮ Cylindrical algebraic sub-decompositions ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ Quantifier elimination for a class of exponential polynomial formulas ⋮ Pole assignment by output feedback using cylindrical algebraic decomposition ⋮ Determination of the tangents for a real plane algebraic curve ⋮ Finding the topology of implicitly defined two algebraic plane curves ⋮ On using Lazard's projection in CAD construction ⋮ Proving inequalities and solving global optimization problems via simplified CAD projection ⋮ A new algorithm for proving global asymptotic stability of rational difference equations ⋮ The complexity of dominating set in geometric intersection graphs ⋮ Partial cylindrical algebraic decomposition for quantifier elimination ⋮ Solution to the generalized champagne problem on simultaneous stabilization of linear systems ⋮ Constructive algebra methods for the \(L_ 2\)-problem for stable linear systems ⋮ Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions ⋮ From approximate factorization to root isolation with application to cylindrical algebraic decomposition ⋮ Validity proof of Lazard's method for CAD construction ⋮ Algorithmic global criteria for excluding oscillations ⋮ Using machine learning to improve cylindrical algebraic decomposition ⋮ Symbolic reachability computation for families of linear vector fields ⋮ Improved projection for cylindrical algebraic decomposition ⋮ Two Variants of Bézout Subresultants for Several Univariate Polynomials ⋮ The computation of polynomial greatest common divisors over an algebraic number field ⋮ Some aspects of complexity in real algebraic geometry ⋮ Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme ⋮ Identifying the parametric occurrence of multiple steady states for some biological networks ⋮ Accelerating parameter synthesis using semi-algebraic constraints ⋮ Faithful real-time animation of parametrized (semi-) algebraic expressions via cylindrical algebraic decomposition ⋮ Truth table invariant cylindrical algebraic decomposition ⋮ Subresultants of several univariate polynomials in Newton basis ⋮ Need Polynomial Systems Be Doubly-Exponential? ⋮ Computing the irreducible real factors and components of an algebraic curve ⋮ Complete numerical isolation of real roots in zero-dimensional triangular systems ⋮ Ambient Isotopic Meshing for Implicit Algebraic Surfaces with Singularities ⋮ The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree ⋮ A Generalised Branch-and-Bound Approach and Its Application in SAT Modulo Nonlinear Integer Arithmetic ⋮ Examples of using dynamic constructible closure. ⋮ An efficient method for analyzing the topology of plane real algebraic curves. ⋮ An efficient algorithm for the stratification and triangulation of an algebraic surface ⋮ Problem Formulation for Truth-Table Invariant Cylindrical Algebraic Decomposition by Incremental Triangular Decomposition ⋮ Applying Machine Learning to the Problem of Choosing a Heuristic to Select the Variable Ordering for Cylindrical Algebraic Decomposition ⋮ A computational method for determining strong stabilizability of \(n\)-D systems ⋮ An exact and efficient approach for computing a cell in an arrangement of quadrics ⋮ Boundary evaluation algorithms for Minkowski combinations of complex sets using topological analysis of implicit curves ⋮ Local box adjacency algorithms for cylindrical algebraic decompositions

This page was built for publication: Cylindrical Algebraic Decomposition I: The Basic Algorithm