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

https://hal.inria.fr/inria-00546856
Contributeur : Nathalie Revol <>
Soumis le : mercredi 15 décembre 2010 - 00:32:53
Dernière modification le : mardi 16 janvier 2018 - 15:57:21
Document(s) archivé(s) le : lundi 5 novembre 2012 - 13:45:16

Fichier

Nguyen-Revol.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

433

Téléchargements de fichiers

290