Cylindrisk algebraisk nedbrytning

I matematik är cylindrisk algebraisk nedbrytning ( CAD ) ett begrepp och en algoritm för att beräkna det, som är grundläggande för datoralgebra och verklig algebraisk geometri . Givet en uppsättning S av polynom i R ⁿ , är en cylindrisk algebraisk sönderdelning en sönderdelning av R ⁿ till anslutna semialgebraiska uppsättningar som kallas celler , på vilka varje polynom har konstant tecken, antingen +, − eller 0. För att vara cylindrisk måste denna sönderdelning uppfylla följande villkor: Om 1 ≤ k < n och π är projektionen från R ⁿ till R ^{n − k} som består i att ta bort de sista k- koordinaterna, så har man för varje cellpar c och d , antingen π ( c ) = π ( d ) eller π ( c ) ∩ π ( d ) = ∅. Detta antyder att bilderna av π av cellerna definierar en cylindrisk sönderdelning av R ^{n − k} .

Begreppet introducerades av George E. Collins 1975, tillsammans med en algoritm för att beräkna den.

Collins algoritm har en beräkningskomplexitet som är dubbelexponentiell i n . Detta är en övre gräns som nås på de flesta poster. Det finns också exempel där det minimala antalet celler är dubbelt exponentiellt, vilket visar att varje allmän algoritm för cylindrisk algebraisk nedbrytning har en dubbel exponentiell komplexitet.

CAD tillhandahåller en effektiv version av kvantifierareliminering över realerna som har en mycket bättre beräkningskomplexitet än den som är ett resultat av det ursprungliga beviset för Tarski–Seidenbergs teorem . Det är tillräckligt effektivt för att implementeras på en dator. Det är en av de viktigaste algoritmerna för beräkningsverklig algebraisk geometri . Att söka efter att förbättra Collins algoritm, eller att tillhandahålla algoritmer som har en bättre komplexitet för delproblem av allmänt intresse, är ett aktivt forskningsfält.

Genomföranden

Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algoritmer i verklig algebraisk geometri. Andra upplagan. Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlin, 2006. x+662 s. ISBN 978-3-540-33098-1 ; 3-540-33098-4
Strzebonski, Adam. Cylindrisk algebraisk nedbrytning från MathWorld .
Cylindrical Algebraic Decomposition i kapitel 6 ("Kombinatorisk rörelseplanering") av planeringsalgoritmer av Steven M. LaValle. Åtkomst 8 februari 2023
Caviness, Bob; Johnson, Jeremy; Kvantifierareliminering och cylindrisk algebraisk nedbrytning . Texter och monografier i symbolisk beräkning. Springer-Verlag, Berlin, 1998.
Collins, George E.: Kvantifierareliminering för den elementära teorin om verkliga slutna fält genom cylindrisk algebraisk nedbrytning, Second GI Conf. Automata Theory and Formal Languages, Springer LNCS 33, 1975.
Davenport, James H.; Heintz, Joos: Real quantifier elimination is double exponential, Journal of Symbolic Computation, 1988. Volym 5, Issues 1–2, ISSN 0747-7171,