Cylindrical Algebraic Decomposition Using Local Projections
| Autor: | Adam Strzebonski |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Computer Science - Symbolic Computation
G.4 Semialgebraic set FOS: Computer and information sciences Dimension of an algebraic variety 0102 computer and information sciences Symbolic Computation (cs.SC) 01 natural sciences Set (abstract data type) Reduction (complexity) Quantifier elimination ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Real algebraic geometry Applied mathematics 0101 mathematics Projection (set theory) Mathematics Discrete mathematics Algebra and Number Theory 010102 general mathematics I.1.2 Cylindrical algebraic decomposition Algebra Computational Mathematics 010201 computation theory & mathematics |
| Zdroj: | ISSAC |
| DOI: | 10.48550/arxiv.1405.4925 |
| Popis: | We present an algorithm which computes a cylindrical algebraic decomposition of a semialgebraic set using projection sets computed for each cell separately. Such local projection sets can be significantly smaller than the global projection set used by the Cylindrical Algebraic Decomposition (CAD) algorithm. This leads to reduction in the number of cells the algorithm needs to construct. A restricted version of the algorithm was introduced in Strzebonski (2014). The full version presented here can be applied to quantified formulas and makes use of equational constraints. We give an empirical comparison of our algorithm and the classical CAD algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|