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:
With Extreme Scale Computing the Rules Have Changed Read chapter Read first chapter

2016 | OriginalPaper | Chapter

On the Implementation of CGS Real QE

Authors : Ryoya Fukasaku, Hidenao Iwane, Yosuke Sato

Published in: Mathematical Software – ICMS 2016

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

A CGS real QE method is a real quantifier elimination (QE) method which is composed of the computation of comprehensive Gröbner systems (CGSs) based on the theory of real root counting. Its fundamental algorithm was first introduced by Weispfenning in 1998. We further improved the algorithm in 2015 so that we can make a satisfactorily practical implementation. For its efficient implementation, there are several key issues we have to take into account. In this extended abstract we introduce them together with some important techniques for making an efficient CGS real QE implementation.

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 Need Polynomial Systems Be Doubly-Exponential?
next chapter Common Divisors of Solvable Polynomials in JAS
Literature
1.
Becker, E., Wörmann, T.: On the trace formula for quadratic forms. In: Recent Advances in Real Algebraic Geometry and Quadratic Forms, Berkeley, CA, 1990/1991; San Francisco, CA, 1991, pp. 271–291. Contemporary Mathematics, vol. 155, American Mathematical Society Providence, RI (1994)
2.
3.
4.
Chen, C., Maza, M.M.: Quantifier elimination by cylindrical algebraic decomposition based on regular chains. In: Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 91–98. ACM (2014)
5.
Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Brakhage, H. (ed.) Automata Theory and Formal Languages. LNCS, vol. 33, pp. 134–183. Springer, Heidelberg (1975)
6.
Dolzmann, A., Gilch, L.A.: Generic hermitian quantifier elimination. In: Buchberger, B., Campbell, J. (eds.) AISC 2004. LNCS (LNAI), vol. 3249, pp. 80–93. Springer, Heidelberg (2004)CrossRef
7.
Fukasaku, R., Iwane, H., Sato, Y.: Real quantifier elimination by computation of comprehensive Gröbner systems. In: Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 2015), pp. 173–180. ACM (2015)
8.
9.
10.
Pedersen, P., Roy, M.-F., Szpirglas, A.: Counting real zeroes in the multivariate case. In: Proceedings of the Effective Methods in Algebraic Geometry, pp. 203–224 (1993)
11.
12.
13.
Suzuki, A., Sato, Y.: A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases. In: Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 2006), pp. 326–331. ACM (2006)
14.
15.
Weispfenning, V.: A new approach to quantifier elimination for real algebra. In: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 376–392. Springer, Vienna (1998)CrossRef
Metadata
Title
On the Implementation of CGS Real QE
Authors
Ryoya Fukasaku
Hidenao Iwane
Yosuke Sato
Copyright Year
2016
Book
Mathematical Software – ICMS 2016

Print ISBN: 978-3-319-42431-6

Electronic ISBN: 978-3-319-42432-3

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-42432-3_21

Premium Partner

    Image Credits