Probabilistic Error Analysis for Inner Products

DOI10.1137/19M1270434MaRDI QIDQ5146629zbMATH OpenOpenAlexFDO

Authors Ilse C. F. Ipsen, Hua Zhou

Publication date 26 January 2021

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.10465

zbMATH Keywords

Azuma's inequalityconcentration boundsmartingalerandom variablesroundoff errors

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Sums of independent random variables; random walks (60G50) Numerical computation of matrix norms, conditioning, scaling (65F35) Roundoff error (65G50)

Abstract: Probabilistic models are proposed for bounding the forward error in the numerically computed inner product (dot product, scalar product) between of two real $n$-vectors. We derive probabilistic perturbation bounds, as well as probabilistic roundoff error bounds for the sequential accumulation of the inner product. These bounds are non-asymptotic, explicit, and make minimal assumptions on perturbations and roundoffs. The perturbations are represented as independent, bounded, zero-mean random variables, and the probabilistic perturbation bound is based on Azuma's inequality. The roundoffs are also represented as bounded, zero-mean random variables. The first probabilistic bound assumes that the roundoffs are independent, while the second one does not. For the latter, we construct a Martingale that mirrors the sequential order of computations. Numerical experiments confirm that our bounds are more informative, often by several orders of magnitude, than traditional deterministic bounds -- even for small vector dimensions~$n$ and very stringent success probabilities. In particular the probabilistic roundoff error bounds are functions of $sqrtn$ rather than~$n$, thus giving a quantitative confirmation of Wilkinson's intuition. The paper concludes with a critical assessment of the probabilistic approach.

Recommendations

• Probabilistic Error Analysis of Approximate Recursive Multipliers
• Inner product rounding error analysis in the presence of underflow
• scientific article; zbMATH DE number 3883514
• A note on error bounds for approximation in inner product spaces
• Probabilistic analysis of an estimator for the Frobenius norm of a matrix product
• Rigorous roundoff error analysis of probabilistic floating-point computations
• scientific article; zbMATH DE number 1070527
• Improved error bounds for inner products in floating-point arithmetic
• scientific article; zbMATH DE number 3986531
• Estimating the error in matrix function approximations

Cites work

• A New Approach to Probabilistic Rounding Error Analysis
• A statistical model of roundoff error for varying length floating-point arithmetic
• A Stochastic Roundoff Error Analysis for the Convolution
• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
• Accuracy and Stability of Numerical Algorithms
• Concentration Inequalities and Martingale Inequalities: A Survey
• scientific article; zbMATH DE number 5704139 (Why is no real title available?)
• scientific article; zbMATH DE number 4074349 (Why is no real title available?)
• scientific article; zbMATH DE number 862514 (Why is no real title available?)
• scientific article; zbMATH DE number 3313188 (Why is no real title available?)
• scientific article; zbMATH DE number 4187014 (Why is no real title available?)
• Numerical inverting of matrices of high order
• On roundoff error distributions in floating point and logarithmic arithmetic
• On roundoff error growth in elliptic problems
• Probabilistic error analysis of Gaussian elimination in floating point and logarithmic arithmetic
• Probability and Computing
• Roundoff error distribution in fixed point multiplication
• Roundoff error for floating point representation of real data
• Tests of probabilistic models for propagation of roundoff errors

Cited in

(22)

• Inner product rounding error analysis in the presence of underflow
• Improved error bounds for inner products in floating-point arithmetic
• scientific article; zbMATH DE number 3883514 (Why is no real title available?)
• scientific article; zbMATH DE number 1240751 (Why is no real title available?)
• scientific article; zbMATH DE number 1070527 (Why is no real title available?)
• Rounding error analysis of mixed precision block Householder QR algorithms
• Newton's method in mixed precision
• Sharper probabilistic backward error analysis for basic linear algebra kernels with random data
• A New Approach to Probabilistic Rounding Error Analysis
• scientific article; zbMATH DE number 4187014 (Why is no real title available?)
• Stochastic rounding and its probabilistic backward error analysis
• Mixed precision algorithms in numerical linear algebra
• Floating-point arithmetic
• Stochastic Rounding Variance and Probabilistic Bounds: A New Approach
• Precision-aware deterministic and probabilistic error bounds for floating point summation
• Numerical stability of algorithms at extreme scale and low precisions
• Probabilistic rounding error analysis of modified Gram-Schmidt
• Rounding error using low precision approximate random variables
• Bounds on nonlinear errors for variance computation with stochastic rounding
• Error analysis of sum-product algorithms under stochastic rounding
• Probabilistic error analysis of limited-precision stochastic rounding
• Rigorous roundoff error analysis of probabilistic floating-point computations

Describes a project that uses

Uses Software

• mctoolbox

This page was built for publication: Probabilistic Error Analysis for Inner Products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146629)