Loading…

A New Approach to Probabilistic Rounding Error Analysis

Traditional rounding error analysis in numerical linear algebra leads to backward error bounds involving the constant γ n = nu/(1 − nu), for a problem size n and unit roundoff u. In the light of large-scale and possibly low-precision computations, such bounds can struggle to provide any useful infor...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific computing 2019-01, Vol.41 (5), p.A2815-A2835
Main Authors: Higham, Nicholas J., Mary, Theo
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Traditional rounding error analysis in numerical linear algebra leads to backward error bounds involving the constant γ n = nu/(1 − nu), for a problem size n and unit roundoff u. In the light of large-scale and possibly low-precision computations, such bounds can struggle to provide any useful information. We develop a new probabilistic rounding error analysis that can be applied to a wide range of algorithms. By using a concentration inequality and making probabilistic assumptions about the rounding errors, we show that in several core linear algebra computations γ n can be replaced by a relaxed constant γ n proportional to √ n log n u with a probability bounded below by a quantity independent of n. The new constant γ n grows much more slowly with n than γn. Our results have three key features: they are backward error bounds; they are exact, not first order; and they are valid for any n, unlike results obtained by applying the central limit theorem, which apply only as n → ∞. We provide numerical experiments that show that for both random and real-life matrices the bounds can be much smaller than the standard deterministic bounds and can have the correct asymptotic growth with n. We also identify two special situations in which the assumptions underlying the analysis are not valid and the bounds do not hold. Our analysis provides, for the first time, a rigorous foundation for the rule of thumb that "one can take the square root of an error constant because of statistical effects in rounding error propagation".
ISSN:1064-8275
1095-7197
DOI:10.1137/18M1226312