A New Approach to Probabilistic Rounding Error Analysis
Nicholas John Higham, Théo Mary · SIAM Journal on Scientific Computing · 2019
Traditional rounding error analysis in numerical linear algebra leads to backward error bounds involving the constant $\gamma^{}_n = nu/(1-nu)$, for a problem size $n$ and unit roundoff $u$. In 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 $\gamma^{}_n$ can be replaced by a relaxed constant $\widetilde{\gamma}^{}_n$ proportional to $\sqrt{n\log n}\,u$ with a probability bounded below by a quantity independent of $n$. The new constant $\widetilde{\gamma}^{}_n$ grows much more slowly with $n$ than $\gamma_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\to\infty$. 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.”