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

https://hal.inria.fr/inria-00546856
Contributor : Nathalie Revol <>
Submitted on : Wednesday, December 15, 2010 - 12:32:53 AM
Last modification on : Tuesday, November 29, 2011 - 1:35:32 PM
Document(s) archivé(s) le : Monday, November 5, 2012 - 1:45:16 PM

File

Nguyen-Revol.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00546856, version 1

Collections

Citation

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〉

Share

Metrics

Record views

425

Document downloads

283