Graphs and stability of algorithms

DOI10.1007/S100920170007MaRDI QIDQ2368627zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 27 September 2006

Published in Calcolo (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s100920170007

zbMATH Keywords

algorithmsbidiagonal systemdependence graphserror boundserror propagationfloating point arithmeticGaussian eliminationpartitioning algorithmrelative equivalent perturbationsrounding error analysistridiagonal systems

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Roundoff error (65G50) Parallel numerical computation (65Y05)

Review text

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).

Recommendations

• scientific article; zbMATH DE number 150454
• Stability aspects in using parallel algorithms
• scientific article; zbMATH DE number 4111908
• On the backward stability of Gauss-Jordan elimination
• Forward error analysis of Gaussian elimination. I: Error and residual estimates

Cited in

(3)

• scientific article; zbMATH DE number 1263371 (Why is no real title available?)
• Notes on the classification of numerical algorithms with respect to their stability to roundoff errors
• When can forward stable algorithms be composed stably?

This page was built for publication: Graphs and stability of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368627)