A New Analysis of Iterative Refinement and its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems
Authors: Erin Carson, Nicholas J. Higham
Journal: SIAM Journal on Scientific Computing
Publication Date: 02 December, 2017
Department of: Mathematics
How to Solve Sensitive Equations Accurately
Some systems of linear equations are ill conditioned: a tiny change in the coefficients can produce a large change in the solution. There is growing interest in using lower precisions such as single or even half precision in climate and weather modeling and machine learning, but this brings an increased likelihood that the linear equations encountered will be very ill conditioned relative to the working precision. Solving such systems accurately in the finite precision arithmetic available on computers is problematic. Researchers at the University of Manchester and the Courant Institute of Mathematical Sciences have found a way to obtain high accuracy without greatly increasing the cost of the standard LU factorization-based solution process. They employ iterative refinement (IR), a long-standing technique for improving the accuracy of a computed solution to a nonsingular linear system $Ax = b$. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix $A$ is not too ill conditioned. This work identifies a mechanism that allows iterative refinement to produce solutions to full machine accuracy even for systems with a numerical singular matrix $A$. Building on a detailed rounding error analysis, an iterative refinement method has been developed that solves the update equations using the GMRES iterative method. The key innovation is to use the computed LU factors as preconditioners, exploiting the information in the factors to greatly reduce the condition number of $A$. In numerical experiments GMRES-IR yields fully accurate solutions in at most $3$ steps in every case.
- Previous analyses of iterative refinement have used a norm inequality that can be very weak. By treating this inequality more carefully this work obtains error bounds that provide more insight.
- The LU factorization of a matrix is equivalent to Gaussian elimination, which is a general form of the elimination of variables method taught at school.
- GMRES (generalized minimal residual algorithm) is a standard iterative algorithm for solving linear systems of equations.
- This work, which is applicable for any precision, shows that, contrary to the conventional wisdom, iterative refinement can provide a highly accurate solution to a linear system $Ax = b$ even when $A$ is a nearly singular matrix.