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.
Document type :
Journal articles
Reliable Computing, Springer Verlag, 2011, 15 (2), pp.120-131
Liste complète des métadonnées

Cited literature [13 references]  Display  Hide  Download
Contributor : Nathalie Revol <>
Submitted on : Wednesday, December 15, 2010 - 12:32:53 AM
Last modification on : Thursday, February 8, 2018 - 11:08:19 AM
Document(s) archivé(s) le : Monday, November 5, 2012 - 1:45:16 PM


Files produced by the author(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〉



Record views


Files downloads