Stefan Wild
Estimating Computational Noise in Iterative Solvers

Mathematics and Computer Science Division
Argonne National Laboratory
9700 S Cass Ave
Argonne Illinois 60439-4844
wild@mcs.anl.gov
Jorge Moré

Computational noise in deterministic simulations is as ill-defined a concept as can be found in scientific computing. The effects (see e.g., [4]) of finite precision arithmetic, discretizations, numerical solutions to systems of equations, and adaptive techniques are typically swept under the rug of most modern simulation codes, the outputs of which we tacitly assume are smooth.

We are motivated by simulation-based optimization problems of the form

$$\min\left\{ f(x)=F[s(x)] : x\in \Omega\subseteq \mathbb{R}^n\right\},$$ (1)

where the objective is determined by the output, $s:\mathbb{R}^n\rightarrow \mathbb{R}^m$, of a numerical simulation. While the function $F$ and the process approximated by $s$ are typically smooth, the computed $f$ is often noisy. In addition to hampering optimization techniques, this computational noise can complicate sensitivity analysis and other applications, which depend on a smooth simulation output.

In this talk we present an algorithm, ECNoise, for quantifying computational noise based on the work of Hamming [3]. Our theoretical framework is based on a model of stochastic noise in univariate functions, but requires only relatively few function evaluations and relies on very few assumptions. In particular, we do not assume any specific distribution forms for the cumulative errors. Our numerical tests suggest the algorithm is also effective for deterministic and multivariate functions.

Given a univariate stochastic $f: \mathbb{R} \rightarrow \mathbb{R}$, we estimate the noise level $\epsilon_f:=\left(\mbox{Var}\{f(t)\}\right)^{1/2}$ by a weighted root-mean-square of $k$-th order differences:

$$\sigma_k = \left(\frac{1}{m-k+1}\frac{(k!)^2}{(2k)!} \sum_{i=0}^{m-k} \left[\Delta^k f(t+ih) \right]^2\right)^{1/2}.$$ (2)

Given a set of $m+1$ function values, ECNoise determines whether the sampling distance $h$ is sufficiently small, and an order $k\leq m$ to estimate $\epsilon_f \approx \sigma_k$. Numerical tests on stochastic functions show that ECNoise generally produces consistent results using as few as $m=6$ additional function evaluations, independent of the dimension.

We illustrate the potential for using ECNoise to gain insight into complex deterministic numerical simulations by considering the fundamental problem of solving a sparse linear system.

• When is the computational noise more than simple round off?
• Is the noise level a property of the solver's operations or the underlying (continuous) function?
• Does demanding a tighter tolerance reduce the noise?

Using the Krylov solvers in MATLAB [1] and the symmetric positive definite matrices in the Florida Sparse Matrix collection [2], we find surprising answers to these and other questions.