×

Probabilistic error analysis for inner products. (English) Zbl 1461.65068

Summary: 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 \(\sqrt{n}\) rather than \(n\), thus giving a quantitative confirmation of Wilkinson’s intuition. The paper concludes with a critical assessment of the probabilistic approach.

MSC:

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

Software:

mctoolbox

References:

[1] I. Babuška and G. Söderlind, On roundoff error growth in elliptic problems, ACM Trans. Math. Software, 44 (2018), 33. · Zbl 1484.65102
[2] E. H. Bareiss and J. L. Barlow, Roundoff error distribution in fixed point multiplication, BIT, 20 (1980), pp. 247-250. · Zbl 0428.65022
[3] J. L. Barlow and E. H. Bareiss, On roundoff error distributions in floating point and logarithmic arithmetic, Computing, 34 (1985), pp. 325-347. · Zbl 0556.65036
[4] J. L. Barlow and E. H. Bareiss, Probabilistic error analysis of Gaussian elimination in floating point and logarithmic arithmetic, Computing, 34 (1985), pp. 349-364. · Zbl 0576.65036
[5] M. Bennani, M.-C. Brunet, and F. Chatelin, 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. · Zbl 0657.65059
[6] M.-C. Brunet and F. Chatelin, CESTAC, a tool for a stochastic round-off error analysis in scientific computing, in Numerical Mathematics and Applications (Oslo, 1985), IMACS Trans. Sci. Comput. 85, I, North-Holland, Amsterdam, 1986, pp. 11-20. · Zbl 1185.65242
[7] D. Calvetti, Roundoff error for floating point representation of real data, Comm. Statist. Theory Methods, 20 (1991), pp. 2687-2695. · Zbl 0775.65004
[8] D. Calvetti, A stochastic roundoff error analysis for the fast Fourier transform, Math. Comp., 56 (1991), pp. 755-774. · Zbl 0729.65116
[9] D. Calvetti, A stochastic roundoff error analysis for the convolution, Math. Comp., 59 (1992), pp. 569-582. · Zbl 0762.65102
[10] F. Chatelin and M.-C. Brunet, A probabilistic round-off error propagation model. Application to the eigenvalue problem, in Reliable Numerical Computation, Oxford University Press, New York, 1990, pp. 139-160. · Zbl 0719.65038
[11] F. Chung and L. Lu, Concentration inequalities and martingale inequalities: A survey, Internet Math., 3 (2006), pp. 79-127. · Zbl 1111.60010
[12] P. Henrici, Problems of stability and error propagation in the numerical integration of ordinary differential equations, in Proceedings of the International Congress of Mathematicians (Stockholm 1962), Institut Mittag-Leffler, Djursholm, 1963, pp. 102-113. · Zbl 0196.49903
[13] N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, PA, 2002. · Zbl 1011.65010
[14] N. J. Higham and T. Mary, A new approach to probabilistic rounding error analysis, SIAM J. Sci. Comput., 41 (2019), pp. A2815-A2835. · Zbl 07123205
[15] T. E. Hull and J. R. Swenson, Tests of probabilistic models for the propagation of roundoff errors, Comm. ACM, 9 (1966), pp. 108-113. · Zbl 0158.15302
[16] W. Kahan, The improbability of probabilistic error analyses for numerical computations, March 1996.
[17] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, Cambridge, UK, 2005. · Zbl 1092.60001
[18] M. Tienari, A statistical model of roundoff error for varying length floating-point arithmetic, BIT, 10 (1970), pp. 355-365. · Zbl 0213.16203
[19] J. von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc., 53 (1947), pp. 1021-1099. · Zbl 0031.31402
[20] J. H. Wilkinson, Rounding errors in algebraic processes, Dover Publications, Inc., New York, 1994. Reprint of the 1963 original (Prentice-Hall, Englewood Cliffs, NJ). · Zbl 0868.65027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.