Accuracy issues in linear algebra using interval arithmetic

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 : In this paper we treat the case of some fundamental interval matrix operations, namely the matrix multiplication and the linear system solving. Interval matrix multiplication implemented naively is very slow, compared to optimized floating-point implementations. Rump has proposed] an algorithm based on the midpoint-radius representation, which costs only 4 floating-point matrix products and provides results with an overestimation factor of at most 1.5. We propose another algorithm to reduce the overestimation factor. This algorithm is based on a decomposition of the operand matrix into two parts, one which is centered in zero and one which does not contain zero. It uses in total 9 floating-point products. We prove that our algorithm provides results with an overestimation factor less than 1.18. In some cases, for example when one of the operand matrices does not contain zero in its interior, our algorithm provides results with no overestimation in exact arithmetic. The other fundamental problem addressed in this presentation is to solve a linear system. Many techniques have been proposed in floating-point arithmetic. We have adapted some of these techniques to interval arithmetic in order to solve a linear system and at the same time certify the solution. The underlying principle of our method is iterative refinement. At the first step, floating-point arithmetic is used to compute an approximate solution to the system. Then we switch to interval arithmetic to compute the residual which helps to refine the error bound using an interval improvement method, namely Jacobi or Gauss-Seidel iterations. This refined error bound serves at the same time as a correction term to the approximate solution, and as the initial value for the next interval improvement. In our method, multiple precision is also employed to increase result accuracy. Classically, double working precision is used for residual computation. Double working precision can also be used to store the approximate solution. First, the working precision is used. Using interval arithmetic, we can easily decide when to switch to the double working precision, that is, when no significant improvement is detected in the error bound. Experimental results show that our method provides results accurate to almost the last bit when the coefficient matrix is not too ill-conditioned. Moreover, we introduce a new technique specific to interval arithmetic, which we shall call the relaxation technique. The nature of this technique is to relax the accuracy on the input while not affecting significantly the result quality, and it helps to increase the performance of the problem. Experimental results show that this technique helps to reduce the execution time significantly without sacrificing accuracy.
Type de document :
Communication dans un congrès
SCAN 2010: 14th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Sep 2010, Lyon, France. 2010
Liste complète des métadonnées
Contributeur : Nathalie Revol <>
Soumis le : jeudi 9 décembre 2010 - 02:15:13
Dernière modification le : vendredi 20 avril 2018 - 15:44:23


  • HAL Id : inria-00544805, version 1



Hong Diep Nguyen, Nathalie Revol. Accuracy issues in linear algebra using interval arithmetic. SCAN 2010: 14th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Sep 2010, Lyon, France. 2010. 〈inria-00544805〉



Consultations de la notice