Publisher DOI: 10.1090/mcom/3355
Title: Sharp estimates for perturbation errors in summations
Language: English
Authors: Lange, Marko 
Rump, Siegfried M. 
Issue Date: 2019
Source: Mathematics of Computation 315 (88): 349-368 (2019)
Journal or Series Name: Mathematics of computation 
Abstract (english): Standard Wilkinson-type error estimates of floating-point algorithms that are solely based on the first or second standard model typically involve a factor γk := ku/(1 - ku), where u denotes the relative rounding error unit of a floating-point number system. Using specific properties of floating-point grids it was shown that often γk can be replaced by ku, and the restriction on k can be removed. That is true for standard algorithms such as summation, dot product, matrix multiplication, and LU- or Cholesky decomposition. Recently it was shown that, at least for summation and dot product, such results derive without any reference to a floating-point grid. In the current paper we further sharpen the error estimate for summation into ku/(1 + ku), again without any reference to a floating-point grid. Furthermore, an estimate of type hu is shown for sums and dot products that are evaluated using a binary tree of height h. Both estimates require a mandatory restriction of size 1/u on the number of summands and the height, respectively. Finally, a different kind of error estimate is shown for recursive summation. The discussed bound is sharp, holds true for any number of summands, and is uniformly bounded by 1. The novelty of our approach is twofold. First, rather than using a rounding function, the discussed estimates are based on almost arbitrary perturbations of real operations without any reference to a floating-point grid. As a consequence, the corresponding floating-point error bounds in some base β for rounding to nearest, and partly also for directed roundings, follow as corollaries. Second, in regard to our weak assumptions, the new estimates are sharp. Our main result is sharp for actual realizations of grids floating-point arithmetics are based on. To be more specific, for any feasible problem size, for IEEE 754 binary32 as well as binary64 format, there are examples satisfying the given bound with equality.
ISSN: 0025-5718
Institute: Zuverlässiges Rechnen E-19 
Type: (wissenschaftlicher) Artikel
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Sep 27, 2020

Google ScholarTM


Add Files to Item

Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.