Compensated summation algorithms are designed to improve the accuracy of ill-conditioned sums. They are based on algorithms, such as FastTwoSum, which are proved to provide, with rounding to nearest, the sum of two fl...
详细信息
Compensated summation algorithms are designed to improve the accuracy of ill-conditioned sums. They are based on algorithms, such as FastTwoSum, which are proved to provide, with rounding to nearest, the sum of two floating-point numbers and the associated rounding error. Discrete stochastic arithmetic enables one to estimate rounding error propagation in numerical codes. It requires a random rounding mode which consists in rounding each computed result toward -infinity or +infinity with the same probability. In this paper we analyse the impact of this random rounding mode on compensated summations based on the FastTwoSum algorithm. We show the accuracy improvement obtained using such compensated summations in numerical simulations controlled with discrete stochastic arithmetic.
The aim of this paper is to find an accurate and efficient algorithm for evaluating the summation of large sets of floating-point numbers. We present a new representation of the floating-point number system in which a...
详细信息
The aim of this paper is to find an accurate and efficient algorithm for evaluating the summation of large sets of floating-point numbers. We present a new representation of the floating-point number system in which a number is represented as a linear combination of integers and the coefficients are powers of the base of the floating-point system. The approach allows to build up an accurate floating-point summation algorithm based on the fact that no rounding error occurs whenever two integer numbers are summed or a floating-point number is multiplied by powers of the base of the floating-point system. The proposed algorithm seems to be competitive in terms of computational effort and, under some assumptions, the computed sum is greatly accurate. With such assumptions, less-conservative in the practical applications, we prove that the relative error of the computed sum is bounded by the unit roundoff. (c) 2006 Elsevier Inc. All rights reserved.
Compensated algorithms consist in computing the rounding errors of individual operations and then adding them later on to the computed result. This makes it possible to increase the accuracy of the computed result eff...
详细信息
Compensated algorithms consist in computing the rounding errors of individual operations and then adding them later on to the computed result. This makes it possible to increase the accuracy of the computed result efficiently. Computing the rounding error of an individual operation is possible through the use of a so-called error-free transformation. In this article, we show that it is possible to use compensated algorithms for having tight interval inclusions. We study compensated algorithms for summation, dot product and polynomial evaluation. We prove that the use of directed rounding makes it possible to get narrow inclusions with compensated algorithms. This is due to the fact that error-free transformations are no more exact but still sufficiently accurate to improve the numerical quality of results.
After a detailed description of the theoretical foundations of forward error analysis formulated by Stummel, the problem of stability of parallel algorithms, which has as yet received very little attention in the lite...
详细信息
After a detailed description of the theoretical foundations of forward error analysis formulated by Stummel, the problem of stability of parallel algorithms, which has as yet received very little attention in the literature, is discussed using arithmetic expressions as an example. The stability analysis includes several summation algorithms, the evaluation of products, parallelization of alternating expressions such as the Horner expression and finite continued fractions and finally general arithmetic expressions. For the CRAY-1 timing versus stability results are given for some of these expressions to classify their numerical quality.
This paper presents a study of some basic blocks needed in the design of floating-point summation algorithms. In particular, in radix-2 floating-point arithmetic, we show that among the set of the algorithms with no c...
详细信息
This paper presents a study of some basic blocks needed in the design of floating-point summation algorithms. In particular, in radix-2 floating-point arithmetic, we show that among the set of the algorithms with no comparisons performing only floating-point additions/subtractions, the 2Sum algorithm introduced by Knuth is minimal, both in terms of number of operations and depth of the dependency graph. We investigate the possible use of another algorithm, Dekker's Fast2Sum algorithm, in radix-10 arithmetic. We give methods for computing, in radix 10, the floating-point number nearest the average value of two floating-point numbers. We also prove that under reasonable conditions, an algorithm performing only round-to-nearest additions/subtractions cannot compute the round-to-nearest sum of at least three floating-point numbers. Starting from an algorithm due to Boldo and Melquiond, we also present new results about the computation of the correctly-rounded sum of three floating-point numbers. For a few of our algorithms, we assume new operations defined by the recent IEEE 754-2008 Standard are available.
Double rounding is a phenomenon that may occur when different floating-point precisions are available on the same system. Although double rounding is, in general, innocuous, it may change the behavior of some useful s...
详细信息
Double rounding is a phenomenon that may occur when different floating-point precisions are available on the same system. Although double rounding is, in general, innocuous, it may change the behavior of some useful small floating-point algorithms. We analyze the potential influence of double rounding on the Fast2Sum and 2Sum algorithms, on some summation algorithms, and Veltkamp's splitting.
This paper presents a study of some basic blocks needed in the design of floating-point summation algorithms. In particular we show that among the set of the algorithms with no comparisons performing only floating-poi...
详细信息
ISBN:
(纸本)9780769536705
This paper presents a study of some basic blocks needed in the design of floating-point summation algorithms. In particular we show that among the set of the algorithms with no comparisons performing only floating-point additions/subtractions, the 2Sum algorithm introduced by Knuth is minimal, both in terms of number of operations and depth of the dependency graph. Under reasonable conditions, we also prove that no algorithms performing only round-to-nearest additions/subtractions exist to compute the round-to-nearest sum of at least three floating-point numbers. Starting from an algorithm due to Boldo and Melquiond, we also present new results about the computation of the correctly-rounded sum of three floating-point numbers.
暂无评论