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:
Introduction Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

5. Enhanced Floating-Point Sums, Dot Products, and Polynomial Values

verfasst von : Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod, Mioara Joldes, Vincent Lefèvre, Guillaume Melquiond, Nathalie Revol, Serge Torres

Erschienen in: Handbook of Floating-Point Arithmetic

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this chapter, we focus on the computation of sums and dot products, and on the evaluation of polynomials in IEEE 754 floating-point arithmetic. Such calculations arise in many fields of numerical computing. Computing sums is required, e.g., in numerical integration and the computation of means and variances. Dot products appear everywhere in numerical linear algebra. Polynomials are used to approximate many functions (see Chapter 10).

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 Basic Properties and Algorithms
Nächstes Kapitel Languages and Compilers
Fußnoten
1
Section 8.​8 will survey how these tasks may be accelerated using specific hardware.
 
2
Under some conditions. See Chapter 4 for more details.
 
3
See the note on underflow, Section 2.​1.​3.
 
4
These bounds are given in [258, p. 82, p. 63, p. 95].
 
5
Which, of course, does not imply that the error itself is halved.
 
6
We also refer to this paper for some interesting examples showing that in practice such bounds are reasonably tight.
 
7
It gives the smallest bound, which does not mean that it will always give the smallest error.
 
8
Indeed, when Kahan introduced his summation algorithm, Theorem 4.​3 of Chapter 4 was not known: Dekker’s paper was published in 1971. Hence, it is fair to say that the Fast2Sum algorithm first appeared in Kahan’s paper, even if it was without the conditions that must be fulfilled for it to always return the exact error of a floating-point addition.
 
9
Priest proves that result in a more general context, just assuming that the arithmetic is faithful and satisfies a few additional properties. See [496] for more details.
 
10
It was then possible to evaluate that error exactly: Dekker’s result was known when Pichat published her paper.
 
11
CRlibm was developed by the Arénaire/AriC team of CNRS, INRIA, and ENS Lyon, France. It is available at https://​gforge.​inria.​fr/​scm/​browser.​php?​group_​id=​5929&​extra=​crlibm.
 
12
This means, in radix 2, that the least significant bit of the significand is a one.
 
Literatur
[24]
I. Babuška. Numerical stability in mathematical analysis. In Proceedings of the 1968 IFIP Congress, volume 1, pages 11–23, 1969.
[36]
M. Bennani and M. C. Brunet. PRECISE: simulation of round-off error propagation model. In 12th World IMACS Congress, July 1988.
[52]
S. Boldo and G. Melquiond. Emulation of FMA and correctly rounded sums: proved algorithms using rounding to odd. IEEE Transactions on Computers, 57(4):462–471, 2008.MathSciNetCrossRef
[76]
W. S. Brown. A simple but realistic model of floating-point computation. ACM Transactions on Mathematical Software, 7(4), 1981.
[81]
[115]
R. M. Corless and N. Fillion. A Graduate Introduction to Numerical Methods, From the Viewpoint of Backward Error Analysis. Springer, 2013.CrossRef
[161]
J. Demmel and H. D. Nguyen. Fast reproducible floating-point summation. In 21th IEEE Symposium on Computer Arithmetic (ARITH-21), pages 163–172, April 2013.
[165]
J. Demmel, P. Ahrens, and H. D. Nguyen. Efficient reproducible floating point summation and BLAS. Technical Report UCB/EECS-2016-121, EECS Department, University of California, Berkeley, June 2016.
[166]
J. Demmel and Y. Hida. Accurate and efficient floating point summation. SIAM Journal of Scientific Computing, 25(4):1214–1248, 2003.MathSciNetCrossRef
[167]
J. Demmel and Y. Hida. Fast and accurate floating point summation with application to computational geometry. Numerical Algorithms, 37(1):101–112, 2004.MathSciNetCrossRef
[222]
S. Graillat, P. Langlois, and N. Louvet. Algorithms for accurate, validated and fast computations with polynomials. Japan Journal of Industrial and Applied Mathematics, 26(2):215–231, 2009.MathSciNetMATH
[223]
S. Graillat, V. Lefèvre, and J.-M. Muller. On the maximum relative error when computing integer powers by iterated multiplications in floating-point arithmetic. Numerical Algorithms, 70:653–667, 2015.MathSciNetCrossRef
[249]
J. R. Hauser. Handling floating-point exceptions in numeric programs. ACM Transactions on Programming Languages and Systems, 18(2):139–174, 1996.CrossRef
[257]
N. J. Higham. The accuracy of floating point summation. SIAM Journal on Scientific Computing, 14(4):783–799, 1993.MathSciNetCrossRef
[258]
N. J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia, PA, 2nd edition, 2002.CrossRef
[266]
T. E. Hull and J. R. Swenson. Test of probabilistic models for propagation of round-off errors. Communications of the ACM, 9:108–113, 1966.MathSciNetCrossRef
[302]
C.-P. Jeannerod and S. M. Rump. Improved error bounds for inner products in floating-point arithmetic. SIAM Journal on Matrix Analysis and Applications, 34(2):338–344, 2013.MathSciNetCrossRef
[303]
C.-P. Jeannerod and S. M. Rump. On relative errors of floating-point operations: optimal bounds and applications. Mathematics of Computation, 2016. To appear.
[339]
[342]
D. E. Knuth. The Art of Computer Programming, volume 2. Addison-Wesley, Reading, MA, 3rd edition, 1998.
[347]
P. Kornerup, V. Lefèvre, N. Louvet, and J.-M. Muller. On the computation of correctly rounded sums. IEEE Transactions on Computers, 61(3):289–298, 2012.MathSciNetCrossRef
[353]
U. W. Kulisch. Circuitry for generating scalar products and sums of floating-point numbers with maximum accuracy. United States Patent 4622650, 1986.
[354]
U. W. Kulisch. Advanced Arithmetic for the Digital Computer: Design of Arithmetic Units. Springer-Verlag, Berlin, 2002.CrossRef
[355]
U. W. Kulisch. Computer Arithmetic and Validity: Theory, Implementation, and Applications. de Gruyter, Berlin, 2008.CrossRef
[361]
M. Lange and S. M. Rump. Error estimates for the summation of real numbers with application to floating-point summation. BIT Numerical Mathematics, 57(3):927–941, 2017.MathSciNetCrossRef
[363]
[367]
P. Langlois. Automatic linear correction of rounding errors. BIT Numerical Algorithms, 41(3):515–539, 2001.MathSciNetCrossRef
[368]
P. Langlois and N. Louvet. How to ensure a faithful polynomial evaluation with the compensated Horner algorithm. In 18th IEEE Symposium on Computer Arithmetic (ARITH-18), pages 141–149, June 2007.
[370]
C. Q. Lauter. Basic building blocks for a triple-double intermediate format. Technical Report 2005-38, LIP, École Normale Supérieure de Lyon, September 2005.
[396]
N. Louvet. Algorithmes Compensés en Arithmétique Flottante: Précision, Validation, Performances. Ph.D. thesis, Université de Perpignan, Perpignan, France, November 2007. In French.
[410]
[454]
A. Neumaier. Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen. ZAMM, 54:39–51, 1974. In German.MathSciNetCrossRef
[471]
T. Ogita, S. M. Rump, and S. Oishi. Accurate sum and dot product. SIAM Journal on Scientific Computing, 26(6):1955–1988, 2005.MathSciNetCrossRef
[472]
T. Ogita, S. M. Rump, and S. Oishi. Verified solutions of linear systems without directed rounding. Technical Report 2005-04, Advanced Research Institute for Science and Engineering, Waseda University, Tokyo, Japan, 2005.
[478]
K. Ozaki, F. Bünger, T. Ogita, S. Oishi, and S. M. Rump. Simple floating-point filters for the two-dimensional orientation problem. BIT Numerical Mathematics, 56(2):729–749, 2016.MathSciNetCrossRef
[479]
K. Ozaki, T. Ogita, F. Bünger, and S. Oishi. Accelerating interval matrix multiplication by mixed precision arithmetic. Nonlinear Theory and its Applications, IEICE, 6(3):364–376, 2015.CrossRef
[490]
M. Pichat. Correction d’une somme en arithmétique à virgule flottante. Numerische Mathematik, 19:400–406, 1972. In French.MathSciNetCrossRef
[495]
D. M. Priest. Algorithms for arbitrary precision floating point arithmetic. In 10th IEEE Symposium on Computer Arithmetic (ARITH-10), pages 132–143, June 1991.
[496]
D. M. Priest. On Properties of Floating-Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. Ph.D. thesis, University of California at Berkeley, 1992.
[521]
S. M. Rump. Ultimately fast accurate summation. SIAM Journal on Scientific Computing, 31(5):3466–3502, 2009.MathSciNetCrossRef
[522]
S. M. Rump. Error estimation of floating-point summation and dot product. BIT Numerical Mathematics, 52(1):201–220, 2012.MathSciNetCrossRef
[525]
S. M. Rump. Computable backward error bounds for basic algorithms in linear algebra. Nonlinear Theory and its Applications, IEICE, 6(3):360–363, 2015.CrossRef
[526]
S. M. Rump and H. Böhm. Least significant bit evaluation of arithmetic expressions in single-precision. Computing, 30:189–199, 1983.MathSciNetCrossRef
[527]
S. M. Rump, F. Bünger, and C.-P. Jeannerod. Improved error bounds for floating-point products and Horner’s scheme. BIT Numerical Mathematics, 56(1):293–307, 2016.MathSciNetCrossRef
[528]
S. M. Rump and C.-P. Jeannerod. Improved backward error bounds for LU and Cholesky factorizations. SIAM Journal on Matrix Analysis and Applications, 35(2):684–698, 2014.MathSciNetCrossRef
[530]
S. M. Rump and M. Lange. On the definition of unit roundoff. BIT Numerical Mathematics, 56(1):309–317, 2016.MathSciNetCrossRef
[531]
S. M. Rump, T. Ogita, and S. Oishi. Accurate floating-point summation part I: Faithful rounding. SIAM Journal on Scientific Computing, 31(1):189–224, 2008.MathSciNetCrossRef
[532]
S. M. Rump, T. Ogita, and S. Oishi. Accurate floating-point summation part II: Sign, K-fold faithful and rounding to nearest. SIAM Journal on Scientific Computing, 31(2):1269–1302, 2008.MathSciNetCrossRef
[634]
J. H. Wilkinson. Rounding Errors in Algebraic Processes. Prentice-Hall, Englewood Cliffs, NJ, 1963.MATH
[644]
G. Zielke and V. Drygalla. Genaue Loesung Linearer Gleichungssysteme. GAMM Mitteilungen der Gesellschaft für Angewandte Mathematik und Mechanik, 26:7–107, 2003.MATH
Metadaten
Titel
Enhanced Floating-Point Sums, Dot Products, and Polynomial Values
verfasst von
Jean-Michel Muller
Nicolas Brunie
Florent de Dinechin
Claude-Pierre Jeannerod
Mioara Joldes
Vincent Lefèvre
Guillaume Melquiond
Nathalie Revol
Serge Torres
Copyright-Jahr
2018
Buch
Handbook of Floating-Point Arithmetic

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

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

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-76526-6_5