Accurate solution of dense linear systems, part I: Algorithms in rounding to nearest

We investigate how extra-precise accumulation of dot products can be used to solve ill-conditioned linear systems accurately. For a given pp-bit working precision, extra-precise evaluation of a dot product means that the products and summation are executed in 2p2p-bit precision, and that the final result is rounded into the pp-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.