Options
Accurate solution of dense linear systems, Part I: Algorithms in rounding to nearest
Publikationstyp
Journal Article
Date Issued
2012-10-27
Sprache
English
Author(s)
Institut
TORE-URI
Volume
242
Issue
1
Start Page
157
End Page
184
Citation
Journal of Computational and Applied Mathematics 1 (242): 157-184 (2013)
Publisher DOI
Scopus ID
Publisher
North-Holland
We investigate how extra-precise accumulation of dot products can be used to solve ill-conditioned linear systems accurately. For a given p-bit working precision, extra-precise evaluation of a dot product means that the products and summation are executed in 2p-bit precision, and that the final result is rounded into the p-bit working precision. Denote by u=2-p the relative rounding error unit in a given working precision. We treat two types of matrices: first up to condition number u-1, and second up to condition number u-2. For both types of matrices we present two types of methods: first for calculating an approximate solution, and second for calculating rigorous error bounds for the solution together with the proof of non-singularity of the matrix of the linear system. In the first part of this paper we present algorithms using only rounding to nearest, in Part II we use directed rounding to obtain better results. All algorithms are given in executable Matlab code and are available from my homepage.
Subjects
(extremely) ill-conditioned
Error analysis
Error-free transformation
Linear system
Rigorous error bounds
Rounding to nearest
DDC Class
510: Mathematik