Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Symbolic Computation and Complexity Theory Transcript of My Talk Read chapter Read first chapter

2014 | OriginalPaper | Chapter

An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions

Authors : Changbo Chen, Marc Moreno Maza

Published in: Computer Mathematics

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations
next chapter Finding the Symbolic Solution of a Geometric Problem Through Numerical Computations
Footnotes
1
More precisely, a multivariate polynomial regarded as a univariate one with respect to its main variable.
 
Literature
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)
Metadata
Title
An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
Authors
Changbo Chen
Marc Moreno Maza
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Book
Computer Mathematics

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

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

Copyright Year: 2014

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

Premium Partner

    Image Credits