https://hal-ens-lyon.archives-ouvertes.fr/ensl-00560188Nguyen, Hong DiepHong DiepNguyenARENAIRE - Computer arithmetic - Inria Grenoble - Rhône-Alpes - Inria - Institut National de Recherche en Informatique et en Automatique - LIP - Laboratoire de l'Informatique du Parallélisme - ENS Lyon - École normale supérieure - Lyon - UCBL - Université Claude Bernard Lyon 1 - Université de Lyon - Inria - Institut National de Recherche en Informatique et en Automatique - Université de Lyon - CNRS - Centre National de la Recherche ScientifiqueEfficient algorithms for verified scientific computing: Numerical linear algebra using interval arithmeticHAL CCSD2011interval arithmeticverified scientific computingcomputing precisionnumerical linear algebra[INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA]Nguyen, Hong Diep2011-01-27 15:39:202023-03-24 14:52:542011-01-27 15:39:20enOther publications1Interval 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.