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:
On the Differential and Full Algebraic Complexities of Operator Matrices Transformations Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree

verfasst von : Matthew England, James H. Davenport

Erschienen in: Computer Algebra in Scientific Computing

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged.
In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Gröbner Bases to move towards the intuitive bound for polynomial degree.

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 A Numerical Method for Computing Border Curves of Bi-parametric Real Polynomial Systems and Applications
Nächstes Kapitel Efficient Simplification Techniques for Special Real Quantifier Elimination with Applications to the Synthesis of Optimal Numerical Algorithms
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
We note that in this quote we made a small correction to the description of the second set of roots (removing a dash from \(y_1\) in the second distinct point). We thank the anonymous referee of the present paper for identifying this correction.
 
2
It would be possible to economise: if \(x_1x_2^2\mapsto \xi _1^2\), then we could map \(x_1^2x_2^4\) to \(\xi _1^4\) rather than a new \(\xi _2^4\). Since this trick is used purely for the analysis and not in implementation, we ignore such possibilities.
 
3
As downloaded from www.​regularchains.​org on 11th March 2016.
 
4
The On-Line Encyclopedia of Integer Sequences, 2010, Sequence A000124, https://​oeis.​org/​A000124.
 
Literatur
1.
Arnon, D., Collins, G.E., McCallum, S.: Cylindrical algebraic decomposition I: the basic algorithm. SIAM J. Comput. 13, 865–877 (1984)MathSciNetCrossRefMATH
2.
Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Algorithms and Computations in Mathematics, vol. 10. Springer, Heidelberg (2006)MATH
3.
Bradford, R., Chen, C., Davenport, J.H., England, M., Moreno Maza, M., Wilson, D.: Truth table invariant cylindrical algebraic decomposition by regular chains. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2014. LNCS, vol. 8660, pp. 44–58. Springer, Heidelberg (2014)
4.
Bradford, R., Davenport, J.H., England, M., McCallum, S., Wilson, D.: Cylindrical algebraic decompositions for boolean combinations. In: Proceedings of ISSAC 2013, pp. 125–132. ACM (2013)
5.
Bradford, R., Davenport, J.H., England, M., McCallum, S., Wilson, D.: Truth table invariant cylindrical algebraic decomposition. J. Symbolic Comput. 76, 1–35 (2016)MathSciNetCrossRefMATH
6.
Bradford, R., Davenport, J.H., England, M., Wilson, D.: Optimising problem formulation for cylindrical algebraic decomposition. In: Carette, J., Aspinall, D., Lange, C., Sojka, P., Windsteiger, W. (eds.) CICM 2013. LNCS, vol. 7961, pp. 19–34. Springer, Heidelberg (2013)CrossRef
7.
8.
Brown, C.W.: Constructing a single open cell in a cylindrical algebraic decomposition. In: Proceedings of ISSAC 2013, pp. 133–140. ACM (2013)
9.
Brown, C.W., Davenport, J.H.: The complexity of quantifier elimination and cylindrical algebraic decomposition. In: Proceedings of ISSAC 2007, pp. 54–60. ACM (2007)
10.
Brown, C.W., El Kahoui, M., Novotni, D., Weber, A.: Algorithmic methods for investigating equilibria in epidemic modelling. J. Symbolic Comput. 41, 1157–1173 (2006)MathSciNetCrossRefMATH
11.
Buchberger, B.: Bruno Buchberger’s PhD thesis (1965): an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symbolic Comput. 41(3–4), 475–511 (2006)MathSciNetCrossRefMATH
12.
Buchberger, B., Hong, H.: Speeding up quantifier elimination by Gröbner bases. Technical report, 91–06. RISC, Johannes Kepler University (1991)
13.
14.
Chen, C., Moreno, M.M., Xia, B., Yang, L.: Computing cylindrical algebraic decomposition via triangular decomposition. In: Proceedings of ISSAC 2009, pp. 95–102. ACM (2009)
15.
Collins, G.E.: The SAC-2 computer algebra system. In: Caviness, B.F. (ed.) EUROCAL 1985. LNCS, vol. 204, pp. 34–35. Springer, Heidelberg (1985)
16.
Collins, G.E.: Quantifier elimination by cylindrical algebraic decomposition - 20 years of progress. In: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition. Texts & Monographs in Symbolic Computation, pp. 8–23. Springer, Heidelberg (1998)CrossRef
17.
Collins, G.E., Hong, H.: Partial cylindrical algebraic decomposition for quantifier elimination. J. Symbolic Comput. 12, 299–328 (1991)MathSciNetCrossRefMATH
18.
Davenport, J.H., Bradford, R., England, M., Wilson, D.: Program verification in the presence of complex numbers, functions with branch cuts etc. In: Proceedings of SYNASC 2012, pp. 83–88. IEEE (2012)
19.
Davenport, J.H., England, M.: Need polynomial systems be doubly-exponential? In: Greuel, G.-M., Koch, T., Paule, P., Sommese, A. (eds.) ICMS 2016. LNCS, vol. 9725, pp. 157–164. Springer, Heidelberg (2016)CrossRef
20.
21.
England, M., Bradford, R., Chen, C., Davenport, J.H., Maza, M.M., Wilson, D.: Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In: Watt, S.M., Davenport, J.H., Sexton, A.P., Sojka, P., Urban, J. (eds.) CICM 2014. LNCS, vol. 8543, pp. 45–60. Springer, Heidelberg (2014)
22.
England, M., Bradford, R., Davenport, J.H.: Improving the use of equational constraints in cylindrical algebraic decomposition. In: Proceedings of ISSAC 2015, pp. 165–172. ACM (2015)
23.
England, M., Wilson, D., Bradford, R., Davenport, J.H.: Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting. In: Hong, H., Yap, C. (eds.) ICMS 2014. LNCS, vol. 8592, pp. 458–465. Springer, Heidelberg (2014)
24.
Erascu, M., Hong, H.: Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation). In: Proceedings of ISSAC 2014, pp. 162–169. ACM (2014)
25.
Faugère, J.C.: A new efficient algorithm for computing groebner bases without reduction to zero (F5). In: Proceedings of ISSAC 2002, pp. 75–83. ACM (2002)
26.
Fotiou, I.A., Parrilo, P.A., Morari, M.: Nonlinear parametric optimization using cylindrical algebraic decomposition. In: 2005 European Control Conference on Decision and Control, CDC-ECC 2005, pp. 3735–3740 (2005)
27.
Han, J., Dai, L., Xia, B.: Constructing fewer open cells by gcd computation in CAD projection. In: Proceedings of ISSAC 2014, pp. 240–247. ACM (2014)
28.
Heintz, J.: Definability and fast quantifier elimination in algebraically closed fields. Theor. Comput. Sci. 24(3), 239–277 (1983)MathSciNetCrossRefMATH
29.
Hong, H.: An improvement of the projection operator in cylindrical algebraic decomposition. In: Proceedings of ISSAC 1990, pp. 261–264. ACM (1990)
30.
Huang, Z., England, M., Davenport, J.H., Paulson, L.: Using machine learning to decide when to precondition cylindrical algebraic decomposition with Groebner bases (2016, to appear)
31.
Huang, Z., England, M., Wilson, D., Davenport, J.H., Paulson, L.C., Bridge, J.: Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. In: Watt, S.M., Davenport, J.H., Sexton, A.P., Sojka, P., Urban, J. (eds.) CICM 2014. LNCS, vol. 8543, pp. 92–107. Springer, Heidelberg (2014)
32.
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)
33.
34.
35.
Mayr, E.W., Meyer, A.R.: The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math. 46(3), 305–329 (1982)MathSciNetCrossRefMATH
36.
Mayr, E.W., Ritscher, S.: Dimension-dependent bounds for gröbner bases of polynomial ideals. J. Symbolic Comput. 49, 78–94 (2013)MathSciNetCrossRefMATH
37.
McCallum, S.: An improved projection operation for cylindrical algebraic decomposition. In: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition. Texts & Monograph in Symbolic Computation, pp. 242–268. Springer, Heidelberg (1998)CrossRef
38.
39.
McCallum, S.: On projection in CAD-based quantifier elimination with equational constraint. In: Proceedings of ISSAC 1999, pp. 145–149. ACM (1999)
40.
McCallum, S.: On propagation of equational constraints in CAD-based quantifier elimination. In: Proceedings of ISSAC 2001, pp. 223–231. ACM (2001)
41.
Paulson, L.C.: MetiTarski: past and future. In: Beringer, L., Felty, A. (eds.) ITP 2012. LNCS, vol. 7406, pp. 1–10. Springer, Heidelberg (2012)
42.
Schwartz, J.T., Sharir, M.: On the “Piano-Movers” problem: I. the case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. Commun. Pure Appl. Math. 36(3), 345–398 (1983)MathSciNetCrossRefMATH
43.
Strzeboński, A.: Cylindrical algebraic decomposition using validated numerics. J. Symbolic Comput. 41(9), 1021–1038 (2006)MathSciNetCrossRefMATH
44.
Strzeboński, A.: Cylindrical algebraic decomposition using local projections. In: Proceedings of ISSAC 2014, pp. 389–396. ACM (2014)
45.
Wilson, D., Bradford, R., Davenport, J.H., England, M.: Cylindrical algebraic sub-decompositions. Math. Comput. Sci. 8, 263–288 (2014)MathSciNetCrossRefMATH
46.
Wilson, D., England, M., Davenport, J.H., Bradford, R.: Using the distribution of cells by dimension in a cylindrical algebraic decomposition. In: Proceedings of SYNASC 2014, pp. 53–60. IEEE (2014)
47.
Wilson, D.J., Bradford, R.J., Davenport, J.H.: Speeding up cylindrical algebraic decomposition by Gröbner bases. In: Jeuring, J., Campbell, J.A., Carette, J., Dos Reis, G., Sojka, P., Wenzel, M., Sorge, V. (eds.) CICM 2012. LNCS, vol. 7362, pp. 280–294. Springer, Heidelberg (2012)CrossRef
Metadaten
Titel
The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree
verfasst von
Matthew England
James H. Davenport
Copyright-Jahr
2016
Buch
Computer Algebra in Scientific Computing

Print ISBN: 978-3-319-45640-9

Electronic ISBN: 978-3-319-45641-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-45641-6_12

Premium Partner

    Bildnachweise