2024/11/19 by Pablo de Oliveira Castro, Castro, Pablo de Oliveira, El-Mehdi El Arar +5
Computer Science · Engineering · #Classical Analysis and ODEs (math.CA) #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Methods and Algorithms #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2411.13601
openalex publication_date 2024/11/19 · openalex created_date 2024/11/20 · openalex updated_date 2026/07/28
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(√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.