Silindirik cebirsel ayrıştırma - Cylindrical algebraic decomposition

Gelen matematik , silindirik cebirsel ayrışma ( CAD ) bir kavram ve bir bir algoritma için temel olan bu hesaplamak için, bilgisayar cebir ve cebirsel geometri . Bir dizi göz önüne alındığında G polinomların R , n , silindirik bir cebirsel ayrışma bir ayrışma olan R , n bağlı olarak semialgebraic setleri olarak adlandırılan hücrelerin ya da 0 olmak - her bir polinom ya +, sabit işareti olan ilgili, silindirik , bu bozunma yerine getirmelidir aşağıdaki şart: Eğer 1 ≤  k  <  n ve π gelen projeksiyonu R n üzerine R , n - k son çıkarılmasında oluşan k her hücre çifti için, daha sonra koordinatları c ve d birine sahiptir, ya da π ( c ) =  π ( d ) veya π ( c ) ∩  π ( d ) = ∅. Bu , hücrelerin π ile görüntülerinin R n - k'nin silindirik bir ayrışmasını tanımladığı  anlamına gelir .

Kavram , 1975'te George E. Collins tarafından , onu hesaplamak için bir algoritma ile tanıtıldı .

Collins'in algoritması, n'de çift ​​üstel olan bir hesaplama karmaşıklığına sahiptir . Bu, çoğu girişte ulaşılan bir üst sınırdır. Minimum hücre sayısının iki kat üstel olduğu, silindirik cebirsel ayrıştırma için her genel algoritmanın çift üstel karmaşıklığa sahip olduğunu gösteren örnekler de vardır.

CAD , Tarski-Seidenberg teoreminin orijinal ispatından elde edilenden çok daha iyi bir hesaplama karmaşıklığına sahip olan gerçekler üzerinde niceleyici elemenin etkili bir versiyonunu sağlar . Bir bilgisayarda uygulanabilecek kadar verimlidir. Hesaplamalı gerçek cebirsel geometrinin en önemli algoritmalarından biridir . Collins'in algoritmasını geliştirmek veya genel ilginin alt problemleri için daha iyi karmaşıklığa sahip algoritmalar sağlamak için araştırma yapmak aktif bir araştırma alanıdır.

Uygulamalar

Referanslar

  • Basu, Saugata; Pollack, Richard; Gerçek cebirsel geometride Roy, Marie-Françoise Algoritmaları. İkinci baskı. Matematikte Algoritmalar ve Hesaplama, 10. Springer-Verlag, Berlin, 2006. x+662 s. ISBN  978-3-540-33098-1 ; 3-540-33098-4
  • Strzebonski, Adam. Silindirik Cebirsel Ayrışma dan MathWorld .
  • Silindirik Cebirsel Ayrışma içinde Planlama algoritmaları Steven M. Lavalle tarafından. 13 Temmuz 2007'de erişildi
  • Kavite, Bob; Johnson, Jeremy; Niceleyici Eliminasyon ve Silindirik Cebirsel Ayrıştırma . Sembolik Hesaplamada Metinler ve Monograflar. Springer-Verlag, Berlin, 1998.
  • Collins, George E.: Silindirik cebirsel ayrıştırma ile gerçek kapalı alanların temel teorisi için niceleyici eleme, Second GI Conf. Otomata Teorisi ve Biçimsel Diller, Springer LNCS 33, 1975.


saplama simgesi

Bu , ilgili cebirsel geometri makale bir taslaktır . Vikipedi'yi genişleterek yardımcı olabilirsiniz .