En matemáticas , la descomposición algebraica cilíndrica ( CAD ) es una noción, y un algoritmo para calcularla, que son fundamentales 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 conectados llamados celdas , en los cuales cada polinomio tiene signo constante, ya sea +, - o 0. Para ser cilíndrico , esta descomposición debe satisfacer la siguiente condición: Si 1 ≤ k < n y π es la proyección de R n en R n - k que consiste en la eliminación de los últimos k coordenadas, a continuación, para cada par de células c y d , se tiene ya sea π ( 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 .
La noción fue introducida por George E. Collins en 1975, junto con un algoritmo para calcularla.
El algoritmo de Collins tiene una complejidad computacional que es doble 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 de descomposición algebraica cilíndrica tiene una complejidad doble exponencial.
CAD proporciona una versión eficaz de la eliminación del cuantificador sobre los reales que tiene una complejidad computacional mucho mejor que la resultante de la demostración original del teorema de Tarski-Seidenberg . Es lo suficientemente eficiente como para implementarse en una computadora. Es uno de los algoritmos más importantes de geometría algebraica real computacional . La búsqueda para mejorar el algoritmo de Collins, o para proporcionar algoritmos que tengan una mayor complejidad para subproblemas de interés general, es un campo activo de investigación.
Implementaciones
Referencias
- Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algoritmos en geometría algebraica real. Segunda edicion. Algoritmos y Computación en Matemáticas, 10. Springer-Verlag, Berlín, 2006. x + 662 págs. 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 algoritmos de planificación por Steven M. LaValle. Consultado el 13 de julio de 2007.
- Caviness, Bob; Johnson, Jeremy; Eliminación de cuantificadores y descomposición algebraica cilíndrica . Textos y monografías en computación simbólica. Springer-Verlag, Berlín, 1998.