Cylindrical Algebraic Decomposition I: The Basic Algorithm
From MaRDI portal
Publication:5187396
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
algorithmcomputational geometryreal algebraic geometrydecision procedurecadzeros of the polynomialscylindrical algebraic decomposition of the Euclidean r-spacepairs of adjacent cells
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
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, 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, Truth table invariant cylindrical algebraic decomposition, 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
