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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Current Challenges in Developing Open Source Computer Algebra Systems Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Precision-Driven Computation in the Evaluation of Expression-Dags with Common Subexpressions: Problems and Solutions

verfasst von : Marc Mörig, Stefan Schirra

Erschienen in: Mathematical Aspects of Computer and Information Sciences

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Precision-driven computation is a recursive scheme for the approximate evaluation of arithmetic expression-dags that allows for specifying the accuracy of evaluation results in advance. We illustrate and explain how current implementations of precision driven arithmetic may negate advantages from sharing common subexpressions by re-evaluating these subexpressions many times. Since the number of re-evaluations depends on seemingly minor details of expression structure and evaluation strategy, significant performance differences may arise between otherwise competitive implementations of precision driven arithmetic for the same user code and then again between otherwise equivalent user codes for the same evaluation strategy as well. We present a new evaluation strategy that separates precision propagation from expression evaluation and thereby avoids multiple evaluations of common subexpressions completely.

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 Another Classroom Example of Robustness Problems in Planar Convex Hull Computation
Nächstes Kapitel Rigorous Numerical Computation of Polynomial Differential Equations Over Unbounded Domains
Literatur
1.
Burnikel, C., Fleischer, R., Funke, S., Mehlhorn, K., Schirra, S., Schmitt, S.: The LEDA class real number - extended version. Technical report, ECG-TR-363110-01, Max-Planck-Institut für Informatik, Saarbrücken, Germany (2005)
2.
Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: Efficient exact geometric computation made easy. In: Proceedings of the 15th Symposium on Computational Geometry (SoCG 1999), pp. 341–350. ACM (1999)
3.
Burnikel, C., Funke, S., Mehlhorn, K., Schirra, S., Schmitt, S.: A separation bound for real algebraic expressions. Algorithmica 55(1), 14–28 (2009)MathSciNetCrossRefMATH
4.
Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.K.: A core library for robust numeric and geometric computation. In: Proceedings of the 15th Symposium on Computational Geometry (SoCG 1999), pp. 351–359. ACM (1999)
5.
Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., Yap, C.K.: Classroom examples of robustness problems in geometric computation. Comput. Geom.: Theory Appl. 40(1), 61–78 (2008)MathSciNetCrossRefMATH
6.
Li, C., Yap, C.K.: A new constructive root bound for algebraic expressions. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 496–505. SIAM (2001)
7.
Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)MATH
8.
Mehlhorn, K., Schirra, S.: Exact computation with leda_real - theory and geometric applications. In: Alefeld, G., Rohn, J., Rump, S.M., Yamamoto, T. (eds.) Symbolic Algebraic Methods and Verification Methods. Springer Mathematics, pp. 163–172. Springer, Wien, Austria (2001)CrossRef
9.
10.
Mörig, M.: Algorithm Engineering for Expression Dag Based Number Types. Ph.D. thesis, Otto-von-Guericke-Universität Magdeburg (2015)
11.
Mörig, M., Rössling, I., Schirra, S.: On the design and implementation of a generic number type for real algebraic number computations based on expression dags. Math. Comput. Sci. 4(4), 539–556 (2010)MathSciNetCrossRefMATH
12.
Pion, S., Yap, C.K.: Constructive root bound for \(k\)-ary rational input numbers. Theor. Comput. Sci. 369(1–3), 361–376 (2006)MathSciNetCrossRefMATH
13.
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Monographs in Computer Science, 1st edn. Springer, New York (1985)CrossRefMATH
14.
Schirra, S.: Robustness and precision issues in geometric computation. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, chap. 14, pp. 597–632. Elsevier, Amsterdam, The Netherlands (2000)
15.
Schirra, S.: Much ado about zero. In: Albers, S., Alt, H., Näher, S. (eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 408–421. Springer, Heidelberg (2009)CrossRef
16.
Schirra, S.: On the use of adaptive, exact decisions number types based on expression-dags in geometric computing. In: 26th Canadian Conference on Computational Geometry (CCCG 2014) (2014)
17.
18.
Yap, C.K.: On guaranteed accuracy computation. In: Geometric Computation, pp. 322–373. World Scientific (2004)
19.
Yap, C.K.: Robust geometric computation. In: Handbook of Discrete and Computational Geometry, 2nd edn., chap. 41, pp. 927–952. CRC (2004)
20.
Yap, C.K., Dubé, T.: The exact computation paradigm. In: Computing in Euclidean Geometry, 2nd edn., pp. 452–486. World Scientific (1995)
21.
Yu, J., Yap, C., Du, Z., Pion, S., Brönnimann, H.: The design of Core 2: a library for exact numeric computation in geometry and algebra. In: Fukuda, K., Hoeven, J., Joswig, M., Takayama, N. (eds.) ICMS 2010. LNCS, vol. 6327, pp. 121–141. Springer, Heidelberg (2010)CrossRef
Metadaten
Titel
Precision-Driven Computation in the Evaluation of Expression-Dags with Common Subexpressions: Problems and Solutions
verfasst von
Marc Mörig
Stefan Schirra
Copyright-Jahr
2016
Buch
Mathematical Aspects of Computer and Information Sciences

Print ISBN: 978-3-319-32858-4

Electronic ISBN: 978-3-319-32859-1

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-32859-1_39

Premium Partner

    Bildnachweise