Solving and Certifying the Solution of a Linear System

Hong Diep Nguyen 1 Nathalie Revol 1
1 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Using floating-point arithmetic to solve a linear system yields a computed result, which is an approximation of the exact solution because of roundoff errors. In this paper, we present an approach to certify the computed solution. Here, "certify" means computing a guaranteed enclosure of the error. Our method is an iterative refinement method and thus it also improves the computed result. The method we present is inspired from the verifylss function of the IntLab library, with a first step, using floating-point arithmetic, to solve the linear system, followed by interval computations to get and refine an enclosure of the error. The specificity of our method is to relax the requirement of tightness of the error, in order to gain in performance. Indeed, only the order of magnitude of the error is needed. Experiments show a gain in accuracy and in performance, for various condition number of the matrix of the linear system.
Type de document :
Article dans une revue
Reliable Computing, Springer Verlag, 2011, 15 (2), pp.120-131
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Nathalie Revol <>
Soumis le : mercredi 15 décembre 2010 - 00:32:53
Dernière modification le : vendredi 20 avril 2018 - 15:44:23
Document(s) archivé(s) le : lundi 5 novembre 2012 - 13:45:16


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00546856, version 1



Hong Diep Nguyen, Nathalie Revol. Solving and Certifying the Solution of a Linear System. Reliable Computing, Springer Verlag, 2011, 15 (2), pp.120-131. 〈inria-00546856〉



Consultations de la notice


Téléchargements de fichiers