Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

On relative errors of floating-point operations: Optimal bounds and applications


Authors: Claude-Pierre Jeannerod and Siegfried M. Rump
Journal: Math. Comp. 87 (2018), 803-819
MSC (2010): Primary 65G50
DOI: https://doi.org/10.1090/mcom/3234
Published electronically: July 7, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Rounding error analyses of numerical algorithms are most often carried out via repeated applications of the so-called standard models of floating-point arithmetic. Given a round-to-nearest function $ \textnormal {fl}$ and barring underflow and overflow, such models bound the relative errors $ E_1(t) = \vert t-\textnormal {fl}(t)\vert/\vert t\vert$ and $ E_2(t) = \vert t-\textnormal {fl}(t)\vert/\vert\textnormal {fl}(t)\vert$ by the unit roundoff $ u$. This paper investigates the possibility and the usefulness of refining these bounds, both in the case of an arbitrary real $ t$ and in the case where $ t$ is the exact result of an arithmetic operation on some floating-point numbers. We show that $ E_1(t)$ and $ E_2(t)$ are optimally bounded by $ u/(1+u)$ and $ u$, respectively, when $ t$ is real or, under mild assumptions on the base and the precision, when $ t = x \pm y$ or $ t = xy$ with $ x,y$ two floating-point numbers. We prove that while this remains true for division in base $ \beta > 2$, smaller, attainable bounds can be derived for both division in base $ \beta =2$ and square root. This set of optimal bounds is then applied to the rounding error analysis of various numerical algorithms: in all cases, we obtain significantly shorter proofs of the best-known error bounds for such algorithms, and/or improvements on these bounds themselves.


References [Enhancements On Off] (What's this?)

  • [1] Richard Brent, Colin Percival, and Paul Zimmermann, Error bounds on complex floating-point multiplication, Math. Comp. 76 (2007), no. 259, 1469-1481 (electronic). MR 2299783, https://doi.org/10.1090/S0025-5718-07-01931-X
  • [2] T. J. Dekker, A floating-point technique for extending the available precision, Numer. Math. 18 (1971/72), 224-242. MR 0299007
  • [3] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1397498
  • [4] G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge, at the University Press, 1952. 2nd ed. MR 0046395
  • [5] Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606
  • [6] J. E. Holm, Floating-Point Arithmetic and Program Correctness Proofs, Ph.D. thesis, Cornell University, Ithaca, NY, August 1980, pp. vii+133.
  • [7] T. E. Hull, T. F. Fairgrieve, and P. T. P. Tang, Implementing complex elementary functions using exception handling, ACM Trans. Math. Software 20 (1994), no. 2, 215-244.
  • [8] Claude-Pierre Jeannerod, Peter Kornerup, Nicolas Louvet, and Jean-Michel Muller, Error bounds on complex floating-point multiplication with an FMA, Math. Comp. 86 (2017), no. 304, 881-898. MR 3584553, https://doi.org/10.1090/mcom/3123
  • [9] Claude-Pierre Jeannerod, Nicolas Louvet, Jean-Michel Muller, and Adrien Panhaleux, Midpoints and exact points of some algebraic functions in floating-point arithmetic, IEEE Trans. Comput. 60 (2011), no. 2, 228-241. MR 2815427, https://doi.org/10.1109/TC.2010.144
  • [10] Claude-Pierre Jeannerod and Siegfried M. Rump, Improved error bounds for inner products in floating-point arithmetic, SIAM J. Matrix Anal. Appl. 34 (2013), no. 2, 338-344. MR 3038111, https://doi.org/10.1137/120894488
  • [11] W. Keller, Prime factors $ k \cdot 2^n + 1$ of Fermat numbers $ {F}_m$ and complete factoring status, August 2016, web page available at http://www.prothsearch.net/fermat.html.
  • [12] Donald E. Knuth, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms; Third edition [of MR0286318], Addison-Wesley, Reading, MA, 1998. MR 3077153
  • [13] P. W. Markstein, Computation of elementary functions on the IBM RISC System/6000 processor, IBM J. Res. Develop. 34 (1990), no. 1, 111-119. MR 1057659, https://doi.org/10.1147/rd.341.0111
  • [14] Takeshi Ogita, Siegfried M. Rump, and Shin'ichi Oishi, Accurate sum and dot product, SIAM J. Sci. Comput. 26 (2005), no. 6, 1955-1988. MR 2196584, https://doi.org/10.1137/030601818
  • [15] Siegfried M. Rump and Claude-Pierre Jeannerod, Improved backward error bounds for LU and Cholesky factorizations, SIAM J. Matrix Anal. Appl. 35 (2014), no. 2, 684-698. MR 3211033, https://doi.org/10.1137/130927231
  • [16] Siegfried Rump, Takeshi Ogita, and Shin'ichi Oishi, Accurate floating-point summation. I. Faithful rounding, SIAM J. Sci. Comput. 31 (2008), no. 1, 189-224. MR 2460776, https://doi.org/10.1137/050645671
  • [17] N. J. A. Sloane and D. W. Wilson, Sequence A019434, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org.
  • [18] Pat H. Sterbenz, Floating-Point Computation, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1974. Prentice-Hall Series in Automatic Computation. MR 0349062
  • [19] J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math. 2 (1960), 319-340. MR 0116477

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65G50

Retrieve articles in all journals with MSC (2010): 65G50


Additional Information

Claude-Pierre Jeannerod
Affiliation: Inria and Université de Lyon, laboratoire LIP (CNRS, ENS de Lyon, Inria, UCBL), 46 allée d’Italie 69364 Lyon cedex 07, France
Email: claude-pierre.jeannerod@inria.fr

Siegfried M. Rump
Affiliation: Hamburg University of Technology, Schwarzenbergstraße 95, Hamburg 21071, Germany — and — Faculty of Science and Engineering, Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo 169-8555, Japan
Email: rump@tuhh.de

DOI: https://doi.org/10.1090/mcom/3234
Received by editor(s): April 20, 2016
Received by editor(s) in revised form: October 26, 2016
Published electronically: July 7, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society