Efficient algorithms for verified scientific computing : Numerical linear algebra using interval arithmetic / Hong Diep Nguyen ; sous la direction de Gilles Villard

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Algèbre linéaire

Arithmétique en virgule flottante

Villard, Gilles (1963-.... ; chercheur en arithmétique informatique) (Directeur de thèse / thesis advisor)

Jaulin, Luc (1967-....) (Président du jury de soutenance / praeses)

Langlois, Philippe (1963-.... ; enseignant-chercheur en informatique) (Rapporteur de la thèse / thesis reporter)

Merlet, Jean-Pierre (1956-....) (Rapporteur de la thèse / thesis reporter)

Revol, Nathalie (19..-.... ; informaticienne) (Membre du jury / opponent)

Rump, Siegfried M. (1955-....) (Membre du jury / opponent)

École normale supérieure de Lyon (2010-...) (Organisme de soutenance / degree-grantor)

École doctorale en Informatique et Mathématiques de Lyon (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire de l'informatique du parallélisme (Lyon ; 1988-....) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : L'arithmétique par intervalles permet de calculer et simultanément vérifier des résultats. Cependant, une application naïve de cette arithmétique conduit à un encadrement grossier des résultats. De plus, de tels calculs peuvent être lents.Nous proposons des algorithmes précis et des implémentations efficaces, utilisant l'arithmétique par intervalles, dans le domaine de l'algèbre linéaire. Deux problèmes sont abordés : la multiplication de matrices à coefficients intervalles et la résolution vérifiée de systèmes linéaires. Pour le premier problème, nous proposons deux algorithmes qui offrent de bons compromis entre vitesse et précision. Pour le second problème, nos principales contributions sont d'une part une technique de relaxation, qui réduit substantiellement le temps d'exécution de l'algorithme, et d'autre part l'utilisation d'une précision étendue en quelques portions bien choisies de l'algorithme, afin d'obtenir rapidement une grande précision.

Résumé / Abstract : Interval arithmetic is a means to compute verified results. However, a naive use of interval arithmetic does not provide accurate enclosures of the exact results. Moreover, interval arithmetic computations can be time-consuming. We propose several accurate algorithms and efficient implementations in verified linear algebra using interval arithmetic. Two fundamental problems are addressed, namely the multiplication of interval matrices and the verification of a floating-point solution of a linear system. For the first problem, we propose two algorithms which offer new tradeoffs between speed and accuracy. For the second problem, which is the verification of the solution of a linear system, our main contributions are twofold. First, we introduce a relaxation technique, which reduces drastically the execution time of the algorithm. Second, we propose to use extended precision for few, well-chosen parts of the computations, to gain accuracy without losing much in term of execution time.