Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Symbolic Computation and Complexity Theory Transcript of My Talk Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions

verfasst von : Changbo Chen, Marc Moreno Maza

Erschienen in: Computer Mathematics

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we propose an incremental algorithm for computing cylindrical algebraic decompositions. The algorithm consists of two parts: computing a complex cylindrical tree and refining this complex tree into a cylindrical tree in real space. The incrementality comes from the first part of the algorithm, where a complex cylindrical tree is constructed by refining a previous complex cylindrical tree with a polynomial constraint. We have implemented our algorithm in Maple. The experimentation shows that the proposed algorithm outperforms existing ones for many examples taken from the literature.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations
Nächstes Kapitel Finding the Symbolic Solution of a Geometric Problem Through Numerical Computations
Fußnoten
1
More precisely, a multivariate polynomial regarded as a univariate one with respect to its main variable.
 
Literatur
1.
Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Springer Lect. Notes Comput. Sci. 33, 515–532 (1975)
2.
Arnon, D.S., Collins, G.E., McCallum, S.: Cylindrical algebraic decomposition II: an adjacency algorithm for the plane. SIAM J. Computing 13(4), 878–889 (1984)MathSciNetCrossRef
3.
Brown, C.W.: Improved projection for cylindrical algebraic decomposition. J. Symb. Comput. 32(5), 447–465 (2001)CrossRefMATH
4.
Caviness, B., Johnson, J. (eds.): Quantifier Elimination and Cylindical Algebraic Decomposition, Texts and Mongraphs in Symbolic Computation. Springer, Berlin (1998)
5.
Hong, H.: An improvement of the projection operator in cylindrical algebraic decomposition. In: ISSAC’90, pp. 261–264. ACM (1990)
6.
McCallum, S.: An improved projection operation for cylindrical algebraic decomposition of 3-dimensional space. J. Symb. Comput. 5(1–2), 141–161 (1988)MathSciNetCrossRefMATH
7.
8.
McCallum, S.: Solving polynomial strict inequalities using cylindrical algebraic decomposition. The Computer Journal 36(5), 432–438 (1993)MathSciNetCrossRefMATH
9.
Strzeboński, A.: Solving systems of strict polynomial inequalities. J. Symb. Comput. 29(3), 471–480 (2000)CrossRefMATH
10.
Collins, G.E., Johnson, J.R., Krandick, W.: Interval arithmetic in cylindrical algebraic decomposition. J. Symb. Comput. 34(2), 145–157 (2002)MathSciNetCrossRefMATH
11.
Dolzmann, A., Seidl, A., Sturm, T.: Efficient projection orders for CAD. In: Proceedings of ISSAC’04, pp. 111–118. ACM (2004)
12.
Brown, C.W., McCallum, S.: On using bi-equational constraints in CAD construction. In: ISSAC’05, pp. 76–83 (2005)
13.
Collins, G.E.: Quantifier elimination by cylindrical algebraic decomposition—twenty years of progress. In: Caviness, B., Johnson, J., (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 8–23. Springer, Berlin (1998)
14.
McCallum, S.: On propagation of equational constraints in CAD-based quantifier elimination. In: Proceedings of ISSAC’01, pp. 223–231 (2001)
15.
McCallum, S., Brown, C.W.: On delineability of varieties in CAD-based quantifier elimination with two equational constraints. In: Proceedings of ISSAC’09, pp. 71–78 (2009)
16.
Brown, C.W.: Qepcad b: a program for computing with semi-algebraic sets using CADs. SIGSAM Bull. 37(4), 97–108 (2003)CrossRefMATH
17.
Hong, H., et al.: QEPCAD B, www.usna.edu/Users/cs/qepcad/
18.
Strzeboński, A.: Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput. 41(9), 1021–1038 (2006)CrossRefMATH
19.
Dolzmann, A., Sturm, T.: Redlog computer algebra meets computer logic. ACM SIGSAM Bull. 31, 2–9 (1996)CrossRef
20.
Iwane, H., Yanami, H., Anai, H., Yokoyama, K.: An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination. In: Proceedings of SNC’2009, pp. 55–64 (2009)
21.
Chen, C., Moreno Maza, M., Xia, B., Yang, L.: Computing cylindrical algebraic decomposition via triangular decomposition. In: ISSAC’09, pp. 95–102 (2009)
22.
McCallum, S.: An improved projection operator for cylindrical algebraic decomposition. In: Caviness, B., Johnson, J., (eds.) Quantifier Elimination and Cylindical Algebraic Decomposition, Texts and Mongraphs in Symbolic Computation. Springer (1998)
23.
Buchberger, B., Hong, H.: Speeding-up quantifier elimination by Gröbner bases. Technical Report 91–06, RISC (Research Institute for Symbolic Computation), Johannes Kepler University, Linz, Austria, Feb 1991
24.
Wilson, D.J., Bradford, R.J., Davenport, J.H.: Speeding up cylindrical algebraic decomposition by Gröbner bases. In: AISC/MKM/Calculemus, pp. 280–294 (2012)
25.
Chen, C.: Solving Polynomial Systems via Triangular Decomposition. PhD thesis, University of Western Ontario (2011)
26.
Chen, C., Moreno Maza, M.: Algorithms for computing triangular decompositions of polynomial systems. In: Proceedings of ISSAC’11, pp. 83–90 (2011)
27.
28.
Strzeboński, A.: Computation with Semialgebraic Sets Represented by Cylindrical Algebraic Formulas. In: Proceedings of ISSAC’2010, pp. 61–68, (2010)
29.
Dahan, X., Moreno Maza, M., Schost, É., Wu, W., Xie, Y.: Lifting techniques for triangular decompositions. In: ISSAC’05, pp. 108–115. ACM Press (2005)
30.
Thomas, J.M.: Differential System. American Mathematical Society, New York (1937)
31.
Wang, D.M.: Decomposing polynomial systems into simple systems. J. Symb. Comp. 25(3), 295–314 (1998)CrossRefMATH
32.
Bächler, T., Gerdt, V., Lange-Hegermann, M., Robertz, D.: Thomas decomposition of algebraic and differential systems. In: Proceedings of CASC’10, pp. 31–54 (2010)
33.
Brown, C.W., Davenport, J.H.: The complexity of quantifier elimination and cylindrical algebraic decomposition. In: Proceedings of ISSAC’07, pp. 54–60
34.
Wang, D.M.: Computing triangular systems and regular systems. J. Sym. Comp. 30(2), 221–236 (2000)CrossRefMATH
35.
36.
37.
Chen, C., Moreno Maza, M.: Algorithms for computing triangular decomposition of polynomial systems. J. Symb. Comput. 47(6), 610–642 (2012)
38.
Boulier, F., Chen, C., Lemaire, F., Moreno Maza, M.: Real root isolation of regular chains. In: Proceedings of ASCM’09, pp. 15–29 (2009)
39.
Chen, C., Golubitsky, O., Lemaire, F., Moreno Maza, M., Pan, W.: Comprehensive triangular decomposition. In: Proceedings of CASC’07, vol. 4770 of Lecture Notes in Computer Science, pp. 73–101. Springer (2007)
Metadaten
Titel
An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
verfasst von
Changbo Chen
Marc Moreno Maza
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Buch
Computer Mathematics

Print ISBN: 978-3-662-43798-8

Electronic ISBN: 978-3-662-43799-5

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-662-43799-5_17