Graphs and stability of algorithms (Q2368627)

The approximate computation in floating point arithmetic can be viewed as an exact computation where not only the input and the output are perturbed, but also the intermediate results are modified according to the relative equivalent perturbations. The relative equivalent perturbations are defined as a solution of a system of equations (nonlinear, in general). The rounding error analysis is performed for algorithms which consist of arithmetic operations only. Such algorithms can be described by their dependence graphs. This allows the author to study the error propagation in a constructive way: The error bounds are then based on some properties of these graphs. In the paper, the author proves two statements which determine two classes of backward stable algorithms. Some examples of the application of the technique are included (Gaussian elimination, a parallel partitioning algorithm for the solution of a bidiagonal system, a sequential and a parallel algorithm for tridiagonal systems).