Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2020;41(4):1726-1741.
doi: 10.1137/19m1270434. Epub 2020 Nov 12.

PROBABILISTIC ERROR ANALYSIS FOR INNER PRODUCTS

Ilse C F Ipsen  1 , Hua Zhou  2
Affiliations

PROBABILISTIC ERROR ANALYSIS FOR INNER PRODUCTS

Ilse C F Ipsen et al. SIAM J Matrix Anal Appl. 2020.

Abstract

Probabilistic models are proposed for bounding the forward error in the numerically computed inner product (dot product, scalar product) between 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 nonasymptotic, explicit, with minimal assumptions, and with a clear relationship between failure probability and relative error. The roundoffs are represented as bounded, zero-mean random variables that are independent or have conditionally independent means. Our probabilistic bounds are based on Azuma's inequality and its associated martingale, which mirrors the sequential order of computations. The derivation of forward error bounds "from first principles" has the advantage of producing condition numbers that are customized for the probabilistic bounds. 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 n rather than n, thus giving a quantitative confirmation of Wilkinson's intuition. The paper concludes with a critical assessment of the probabilistic approach.

Keywords: 60G42; 60G50; 65F30; 65G50; Azuma’s inequality; concentration bounds; martingale; random variables; roundoff errors.

PubMed Disclaimer

Figures

Fig. 5.1.
Fig. 5.1.
Comparison of probabilistic bound (red 5.2) with deterministic bound (blue 5.1) and relative error (green) versus vector dimensions 1 ≤ n ≤ 108 in steps of 106. Vertical axis starts at 10−8 and ends at 108. Elements can have different signs.
Fig. 5.2.
Fig. 5.2.
Comparison of probabilistic bound (red 5.2) with deterministic bound (blue 5.1) and relative error (green) versus vector dimensions 1 ≤ n ≤ 108 in steps of 106. Vertical axis starts at 10−8 and ends at 108. All elements have the same sign.
Fig. 5.3.
Fig. 5.3.
Comparison of probabilistic bound (red 5.4) with deterministic bound (blue 5.3) and relative error (green) versus vector dimensions 1 ≤ n ≤ 108 in steps of 106. Vertical axis starts at 10−8 and ends at 108. All elements have the same sign.
Fig. 5.4.
Fig. 5.4.
Comparison of probabilistic bound (red 5.4) with deterministic bound (blue 5.3) and relative error (green) versus vector dimensions 1 ≤ n ≤ 108 in steps of 106. Vertical axis starts at 10−8 and ends at 108. All elements have the same sign.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

References

    1. Babuška I and Söderlind G, On roundoff error growth in elliptic problems, ACM Trans. Math. Software, 44 (2018), 33.
    1. Bareiss EH and Barlow JL, Roundoff error distribution in fixed point multiplication, BIT, 20 (1980), pp. 247–250.
    1. Barlow JL and Bareiss EH, On roundoff error distributions in floating point and logarithmic arithmetic, Computing, 34 (1985), pp. 325–347.
    1. Barlow JL and Bareiss EH, Probabilistic error analysis of Gaussian elimination in floating point and logarithmic arithmetic, Computing, 34 (1985), pp. 349–364.
    1. Bennani M, Brunet M-C, and Chatelin F, De l’utilisation en calcul matriciel de modèles probabilistes pour la simulation des erreurs de calcul, C. R. Math. Acad. Sci. Paris, 307 (1988), pp. 847–850.

LinkOut - more resources