Error-free computer solution of certain system of linear equations (Q1091753)

The authors develop 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 is based on an easily programmed method developed earlier by \textit{O. Aberth} [ibid. 4, 285-288 (1978; Zbl 0419.65024)]. This procedure 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. As a byproduct of the Gaussian elimination process, a computable upper bound for \(| \det (A)|\) is obtained, which is an alternative to using Hadamard's inequality.