Error-free computer solution of certain systems of linear equations

In this article we propose a procedure which generates the exact solution for the system Ax = b, where A is an integral nonsingular matrix and b is an integral vector, by improving the initial floating-point approximation to the solution. This procedure, based on an easily programmed method proposed by Aberth 1], first computes the approximate floating-point solution x^* by using an available linear equation solving algorithm. Then it extracts the exact solution x from x^* if the error in the approximation x^* is sufficiently small. An a posteriori upper bound for the error of x^* is derived when Gaussian Elimination with partial pivoting is used. Also, a computable upper bound for |det(A)|, which is an alternative to using Hadamard's inequality, is obtained as a byproduct of the Gaussian Elimination process.