Hispanopedia WikiEn matemáticas , la descomposición algebraica cilíndrica ( CAD ) es una noción, junto con un algoritmo para calcularla, que es fundamental para el álgebra computacional y la geometría algebraica real . Dado un conjunto S de polinomios en R n , una descomposición algebraica cilíndrica es una descomposición de R n en conjuntos semialgebraicos conexos llamados celdas , en los que cada polinomio tiene signo constante, ya sea +, − o 0. Para ser cilíndrica , esta descomposición debe satisfacer la siguiente condición: Si 1 ≤ k < n y π es la proyección de R n sobre R n − k que consiste en eliminar las últimas k coordenadas, entonces para cada par de celdas c y d , se tiene π ( c ) = π ( d ) o π ( c ) ∩ π ( d ) = ∅. Esto implica que las imágenes por π de las celdas definen una descomposición cilíndrica de R n − k .
El concepto fue introducido por George E. Collins en 1975, junto con un algoritmo para calcularlo.
El algoritmo de Collins tiene una complejidad computacional que es doblemente exponencial en n . Este es un límite superior que se alcanza en la mayoría de las entradas. También hay ejemplos en los que el número mínimo de celdas es doblemente exponencial, lo que demuestra que todo algoritmo general para la descomposición algebraica cilíndrica tiene una complejidad doblemente exponencial.
El CAD proporciona una versión eficaz de la eliminación de cuantificadores sobre los números reales que tiene una complejidad computacional mucho mejor que la resultante de la prueba original del teorema de Tarski-Seidenberg . Es lo suficientemente eficiente como para ser implementado en una computadora. Es uno de los algoritmos más importantes de la geometría algebraica real computacional . La búsqueda de mejoras en el algoritmo de Collins, o de proporcionar algoritmos que tengan una mejor complejidad para subproblemas de interés general, es un campo activo de investigación.
Implementaciones
- Mathematica : Descomposición cilíndrica
- QEPCAD - Eliminación de cuantificadores mediante descomposición algebraica cilíndrica parcial
- registro rojo
- Maple : la biblioteca RegularChains y ProjectionCAD
Referencias
- Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algoritmos en geometría algebraica real. Segunda edición. Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlín, 2006. x+662 pp. ISBN 978-3-540-33098-1 ; 3-540-33098-4
- Strzebonski, Adam. Descomposición algebraica cilíndrica de MathWorld .
- Descomposición algebraica cilíndrica en el capítulo 6 ("Planificación del movimiento combinatorio") de Algoritmos de planificación de Steven M. LaValle. Consultado el 8 de febrero de 2023
- Caviness, Bob; Johnson, Jeremy; Eliminación de cuantificadores y descomposición algebraica cilíndrica. Textos y monografías sobre computación simbólica. Springer-Verlag, Berlín, 1998.
- Collins, George E.: Eliminación de cuantificadores para la teoría elemental de campos reales cerrados mediante descomposición algebraica cilíndrica, Segunda Conferencia GI. Teoría de autómatas y lenguajes formales, Springer LNCS 33, 1975.
- Davenport, James H.; Heintz, Joos : La eliminación del cuantificador real es doblemente exponencial, Journal of Symbolic Computation, 1988. Volumen 5, números 1-2, ISSN 0747-7171,