Accurate solution of dense linear systems, Part II: Algorithms using directed rounding

Abstract. 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 = 2p the relative rounding error unit in a given working precision. We treat two types of matrices: first up to condition number u1, and second up to condition number u2. 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. Key words. Linear systems, rounding to nearest, (extremely) ill-conditioned, error-free transformation, error analysis, rigorous error bounds. AMS subject classications. 65F05, 65G20 1. Introduction and notation. The solution of a linear system Ax = b is a ubiquitous task in numerical computations. In Part I and II of this paper we present different methods to compute guaranteed error bounds for the solution of a linear system, i.e. with a certied accuracy. The methods in this Part