Error Analysis of Sum-Product Algorithms under Stochastic Rounding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915467036196864 |
|---|---|
| author | Castro, Pablo de Oliveira Arar, El-Mehdi El Petit, Eric Sohier, Devan |
| author_facet | Castro, Pablo de Oliveira Arar, El-Mehdi El Petit, Eric Sohier, Devan |
| contents | The quality of numerical computations can be measured through their forward error, for which finding good error bounds is challenging in general. For several algorithms and using stochastic rounding (SR), probabilistic analysis has been shown to be an effective alternative for obtaining tight error bounds. This analysis considers the distribution of errors and evaluates the algorithm's performance on average. Using martingales and the Azuma-Hoeffding inequality, it provides error bounds that are valid with a certain probability and in O($\sqrt$nu) instead of deterministic worst-case bounds in O(nu), where n is the number of operations and u is the unit roundoff. In this paper, we present a general method that automatically constructs a martingale for any computation scheme with multi-linear errors based on additions, subtractions, and multiplications. We apply this generalization to algorithms previously studied with SR, such as pairwise summation and the Horner algorithm, and prove equivalent results. We also analyze a previously unstudied algorithm, Karatsuba polynomial multiplication, which illustrates that the method can handle reused intermediate computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_13601 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Error Analysis of Sum-Product Algorithms under Stochastic Rounding Castro, Pablo de Oliveira Arar, El-Mehdi El Petit, Eric Sohier, Devan Computation Data Structures and Algorithms Classical Analysis and ODEs The quality of numerical computations can be measured through their forward error, for which finding good error bounds is challenging in general. For several algorithms and using stochastic rounding (SR), probabilistic analysis has been shown to be an effective alternative for obtaining tight error bounds. This analysis considers the distribution of errors and evaluates the algorithm's performance on average. Using martingales and the Azuma-Hoeffding inequality, it provides error bounds that are valid with a certain probability and in O($\sqrt$nu) instead of deterministic worst-case bounds in O(nu), where n is the number of operations and u is the unit roundoff. In this paper, we present a general method that automatically constructs a martingale for any computation scheme with multi-linear errors based on additions, subtractions, and multiplications. We apply this generalization to algorithms previously studied with SR, such as pairwise summation and the Horner algorithm, and prove equivalent results. We also analyze a previously unstudied algorithm, Karatsuba polynomial multiplication, which illustrates that the method can handle reused intermediate computations. |
| title | Error Analysis of Sum-Product Algorithms under Stochastic Rounding |
| topic | Computation Data Structures and Algorithms Classical Analysis and ODEs |
| url | https://arxiv.org/abs/2411.13601 |