.png){kind=icon}
.png){kind=icon}
Return
BOUNDS ON NONLINEAR ERRORS FOR VARIANCE COMPUTATION WITH STOCHASTIC ROUNDING
.png){kind=icon}
OA
AI
DOI：10.1137/23M1563001.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The main objective of this work is to investigate nonlinear errors and pairwise summation using stochastic rounding (SR) in variance computation algorithms. We estimate the forward error of computations under SR through two methods: the first is based on a bound of the variance and the Bienayme'--Chebyshev inequality, while the second is based on martingales and the Azuma--Hoeffding inequality. The study shows that for pairwise s ummation, using SR results in a probabilistic bound of the forward error proportional to log(n)u rather than the deterministic bound in O(root log(n)u) when using the default rounding mode. We examine two algorithms that compute the variance, one called ``textbook and the other ``two-pass, which both exhibit nonlinear errors. Using the two methods mentioned above, we show that the forward errors of these algorithms have probabilistic bounds under SR in O(root nu ) instead of nu for the deterministic bounds. We show that this advantage holds using pairwise summation for both textbook and two-pass, with probabilistic bounds of the forward error proportional to root log(n)u.
Keywords:
stochastic rounding
floating-point arithmetic
vari- ance computation
nonlinear error
Doob--Meyer decomposition
pair- wise summation
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W