Probabilistic Error Analysis for Inner Products

DOI10.1137/19M1270434zbMATH Open1461.65068arXiv1906.10465OpenAlexW3104818416MaRDI QIDQ5146629FDOQ5146629

Hua Zhou, Ilse C. F. Ipsen

Publication date: 26 January 2021

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

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.

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

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

zbMATH Keywords

martingalerandom variablesroundoff errorsAzuma's inequalityconcentration bounds

Mathematics Subject Classification ID

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

Cites Work

• Accuracy and Stability of Numerical Algorithms
• Concentration Inequalities and Martingale Inequalities: A Survey
• Probability and Computing
• Numerical inverting of matrices of high order
• Title not available (Why is that?)
• On roundoff error distributions in floating point and logarithmic arithmetic
• Tests of probabilistic models for propagation of roundoff errors
• Title not available (Why is that?)
• Probabilistic error analysis of Gaussian elimination in floating point and logarithmic arithmetic
• A statistical model of roundoff error for varying length floating-point arithmetic
• A New Approach to Probabilistic Rounding Error Analysis
• A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
• Title not available (Why is that?)
• A Stochastic Roundoff Error Analysis for the Convolution
• On Roundoff Error Growth in Elliptic Problems
• Title not available (Why is that?)
• Roundoff error for floating point representation of real data
• Title not available (Why is that?)
• Roundoff error distribution in fixed point multiplication

Cited In (15)

• Probabilistic rounding error analysis of modified Gram-Schmidt
• Mixed precision algorithms in numerical linear algebra
• Rounding error using low precision approximate random variables
• Floating-point arithmetic
• Stochastic Rounding Variance and Probabilistic Bounds: A New Approach
• Title not available (Why is that?)
• Bounds on nonlinear errors for variance computation with stochastic rounding
• Title not available (Why is that?)
• Rounding Error Analysis of Mixed Precision Block Householder QR Algorithms
• Stochastic Rounding and Its Probabilistic Backward Error Analysis
• Precision-aware deterministic and probabilistic error bounds for floating point summation
• Numerical stability of algorithms at extreme scale and low precisions
• Newton's Method in Mixed Precision
• Rigorous roundoff error analysis of probabilistic floating-point computations
• Inner product rounding error analysis in the presence of underflow

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)